시간 복잡도(Time Complexity)

시간 복잡도는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. -위키피디아

컴퓨터 과학에서 비효율적인 알고리즘을 사용하게 되면 경우에 따라서는 현재 컴퓨터 성능 기준으로 수억년이 걸릴 수 있다고 한다.

 

constant	logarithmic	linear	quadratic	expoential
O(1)	O(log n)	O(n)	O(n^2)	O(c^n)

 

array 
- index 로 접근시 바로 접근 가능, 할당할 때도 O(1)
- 추가, 삭제 하는 경우 기존 데이터의 위치를 재조정해야하므로 O(n)
- 값을 찾는 경우(인덱스X) 처음부터 검색해야 하므로 O(n)

Linked list
- 헤드(HEAD)를 알아야 한다. 
- 값을 찾을 때는 헤드에서부터 찾아가는 방식이므로 찾기, 할당 O(n)
- 추가할 때는 (이미 위치를 찾았다는 가정하에) 노드를 연결 또는 해제만 해주면 되므로 O(1)
- 삭제할 때는 (이미 위치를 찾았다는 가정하에) 
   ㄴ 싱글링크드인 경우 head: O(1), middle (중간노드): O(n)
   ㄴ 더블링크드인 경우 O(1)
- 레퍼런스가 없는 노드는 가비지 컬렉터에 의해 정리된다.

* array, Linked list 비교

	추가	인덱스 조회
array	느림	빠름
Linked list	빠름	느림

Trees
- 일반 트리인 경우 O(n)
- 이진 탐색 트리인 경우 검색, 삭제시 O(log n) 
   ㄴ 추가시, 최악의 경우 편향된 구조가 나오므로 O(n)
   ㄴ 그래서 균형을 맞춰주는 방법을 사용한다. (AVL 알고리즘)
   ㄴ 각 부모 노드가 왼쪽, 오른쪽 자식 가지의 차이가 2 이상 되지 않게 함.

 

 

HashTable

- 값을 찾을 때 최적인 경우 O(1)

- 삭제하는 경우 최적인 경우 O(1)