시간복잡도

자료구조에 대해서 조회, 삽입, 변경(수정), 제거를 수행할 때 걸리는 시간과 입력의 함수 관계를 나타낸다.

big-O

최악의 경우를 기준으로 시간 복잡도를 나타냄.

크기 비교(내림차순)
O(n!) > O(2^n) > O(n^2) > O(nlog n) > O(n) > O(log n) > O(1)

O(log n) < O(n) 항상 성립한다?

'항상'은 아니다....단순히 값의 크기만 비교하는게 아니라
증가량의 차이도 고려하는 것 같다. (내용추가)

big-Omega = 최선의 경우를 다루는 표기법 (하한점근선?)

big-Theta = 최악, 최선의 중간경우를 다루는 표기법

종류는 이정도만 알고 넘어가자

자료구조별 시간복잡도

배열

Insert - O(n) 0번 인덱스에 삽입시 나머지 값은 모두 뒤로 밀려야 하므로
Lookup (position) - O(1) 인덱스를 알고있을 때
Assign(덮어씌우기) - O(1)
Remove - O(n) 0번 인덱스를 제거했을 때 other 인덱스를 하나씩 땡겨줘야 하므로
Find(value) - O(n) 값만 알고 배열안에서 찾을 때 모두 순환해야 하므로

단일 연결리스트

Lookup - O(n)
Find - O(n)
Assign - O(n)
Insert - O(1) 추가하려는 위치만 알면 next노드를 알 수 있으므로 상수 시간복잡도가 나온다
Remove - (head) O(1)
- (middle) O(n) 이전 노드를 알 수 없으므로

이중연결리스트

Lookup - O(n)
Find - O(n)
Assign - O(n)
Insert - O(1)
Remove - O(1)

결론

배열 : Insert 상수시간 / Insert, Remove는 선형시간
단일 연결리스트 : Insert 상수시간 / Lookup, remove 선형시간
이중 연결리스트 : Insert, Remove 상수시간 / 노드가 더큰 메모리공간을 사용함(방향이 2개)

트리

Find - O(n)

이진 탐색 트리 (BST)

BST의 데이터가 random하게 구성된다고 가정했을 때, 평균 트리의 높이는 O(log n)이 된다.
Lookup, Insert, Remove 연산의 시간 복잡도가 O(log n)이 된다는 의미.

따라서, BST에 Insert나 Remove가 일어날 때 트리의 균형을 잡아줌으로써 높이를 log n 으로 유지하면 된다.

Find - O(log n)
탐색값이 현재 노드 값과 비교했을 때 서브트리를 탐색하게 되므로 한번 비교할 때마다 탐색해야 하는 양이 절반으로 줄어든다
정확하게는 밑이 2인 log n의 복잡도를 갖는다
대부분 연산 - O(h) h는 트리의 높이

최악의 경우 노드 추가, 삭제, 조회의 시간복잡도
정렬이 안됐고, 이진 탐색 트리의 형태가 아닌 단일 연결리스트의 형태일 때

추가: O(N)
삭제: O(N)
조회: O(N)

이진 탐색 트리를 정렬된 배열 대신 사용하는 이유

트리는 메모리의 공간을 연속적으로 사용하지 않고, insert & remove 를 수행할 때 이진 탐색 트리가 정렬된 배열보다 더 효율적이다.