자료구조에 대하여 - 1

_1. 시간 복잡도란?

 

 

[ 시간 복잡도 ]

• 입력값과 연산 수행 시간의 상관관계를 나타내는 척도

 

 

 

[ 시간 복잡도에 사용되는 표기법 ]

• Big-O 👉👉 최악의 경우를 나타냄 (상한 접근)
  
  • O(n): 최악의 경우 n번까지 수행되면 프로그램을 끝낼 수 있다.
• Big-Omega 👉👉 최적의 경우를 나타냄 (하한 접근)
  
  • O(n): 최소 n번은 수행되어야 프로그램을 끝낼 수 있다.
• Theta  👉👉 평균 (Big-O 와 Big-Omega값의 평균값)

 

 

[ 빅오 표기법 ]

(Better)    O(1) < O(log n) < O(n) < O(n×log n) < O(n^2) < O(2^n) < O(n!)    (Worse)

               상수 함수 < 로그 함수 < 선형 함수 < 다항 함수 < 지수 함수 < 재귀 함수

 

 

 

[ 빅오 표기법별 대표 알고리즘]

• O(1): Operation push and pop on Stack
• O(log n): Binary Tree
• O(n): for loop
• O(n×log n): Quick Sort, Merge Sort, Heap Sort
• O(n2): Double for loop, Insert Sort, Bubble Sort, Selection Sort
• O(2n): Fibonacci Sequence

 

 

 

 

[ 자료구조의 시간복잡도 ]

 

[ 정렬의 시간복잡도 ]

 

 

 

---

_2. 배열과 링크드 리스트의 차이를 설명해주세요.

 

 

[ 배열 ]

• 데이터들이 메모리공간에 연속적으로 저장
  • index를 통한 Random access 가능
    • 데이터 접근이 빠름
• 배열의 크기는 생성 이후 변경 불가
• 데이터 삽입 삭제에 취약

 

 

 

[ 링크드 리스트 ]

• 데이터가 메모리에 연속적으로 저장되어있지 않음 (어딘가에 저장)
  • Sequential Access만 가능
    • 데이터 접근이 배열에 비해 느림
• 크기를 동적으로 변경 가능
• 데이터 삽입 삭제에 용이
• 데이터와 다음 노드를 가리키는 포인터로 이루어진 노드가 연결된 형태

 

 

---

_3. Hash Function, HashTable에 대해서 설명해주세요.

 

 

[ Hash Function 해시 함수 ]

• 데이터의 효율적 관리를 목적으로 임의의 길이의 데이터를 고정된 길이의 데이터로 매핑하는 함수
• 키(key) 👉 매핑 전 원래 데이터의 값
• 해시값(hash value) 👉 매핑 후 데이터의 값
• 해싱(hashing) 👉 매핑하는 과정

 

 

 

[ Hash Function 해시 함수 장점 ]

• 적은 리소스로 많은 데이터를 효율적으로 관리
  • 무한에 가까운 데이터(키)들을 유한한 개수의 해시값으로 매핑함으로써 관리
• 색인(index)에 해시값을 사용함으로써 모든 데이터를 살피지 않아도 검색과 삽입/삭제를 빠르게 수행
• 해시함수는 언제나 동일한 해시값을 리턴하고, 해당 색인만 알면 해시테이블의 크기에 상관없이 데이터에 대단히 빠르게 접근

 

[ Hash Function 해시 함수 단점 ]

• 해시함수가 서로 다른 두 개의 키에 대해 동일한 해시값을 내는 해시충돌(collision)이 발생
  • 👉  해시함수는 해쉬값의 개수보다 대개 많은 키값을 해쉬값으로 변환(many-to-one 대응)하기 때문

 

 

 

 

 

 

[ Hash Table 해시 테이블 ]

• 해시함수를 사용하여 키를 해시값으로 매핑하고, 이 해시값을 색인(index) 혹은 주소 삼아 데이터의 값(value)을 키와 함께 저장하는 자료구조
• 버킷(bucket) or 슬롯(slot) 👉 데이터가 저장되는 곳

 

위 예시 그림의 버킷

 

 

 

 

 

---

출처

https://todaycode.tistory.com/45

시간 복잡도란?

https://bangu4.tistory.com/202

시간복잡도 - 총정리

https://hongcoding.tistory.com/74

배열과 연결리스트 (Array & LinkedList)

https://wooono.tistory.com/281

[자료구조] Linked List(연결 리스트) 와 Array(배열)의 차이

https://m.blog.naver.com/raylee00/221944085465

연결리스트(Linked List)와 배열(Array), 그리고 시간복잡도의 차이에 대해

https://ratsgo.github.io/data%20structure&algorithm/2017/10/25/hash/

해싱, 해시함수, 해시테이블 · ratsgo's blog