개념
시간복잡도(Time Complexity)는 어떤 문제를 해결하는데 걸리는 시간과 입력의 함수관계를 의미한다. 어떤 알고리즘을 수행하는데 필요한 기본 연산이 얼마만큼의 시간이 걸린다고 할 때, 기본연산의 최대 개수를 나타낸다.
시간복잡도는 입력의 크기에 따라 다양해질 수 있기 때문에 측정방법도 다양하다. 주로 사용되는 방법은 모든 입력에 대해 걸리는 최대의 시간을 측정하는 최악의 시간 복잡도(worst-case complexity, T(n))와 모든 입력에 대해 걸리는 시간의 평균을 측정하는 평균 시간 복잡도(average-case complexity)가 있다.
Big-O 표기법을 사용하여 나타내고, 입력이 n 일 때 다음과 같이 표기할 수 있다. O(1), O(n), O(log n)...
자바스크립트를 이용해
시간 복잡도의 종류
상수 시간(Constant time), O(1)
어떤 알고리즘 T(n)이 입력의 개수나 크기에 구애받지 않는 값에 의해서 정해지는 경우 이 알고리즘의 시간복잡도는 O(1)이라고 한다. 예를 들어 배열에서 특정 인덱스의 값을 읽거나 링크드 리스트에 데이터를 삽입/제거 할 때
로그 시간(logarithmic time), O(logn)
T(n) = O(logn)인 경우 로그 시간이 걸린다고 한다. 어떤 알고리즘의 시간 복잡도가 로그 시간을 가질때, 높은 효율의 알고리즘이라고 할 수 있는데, 그 이유는 로그 함수처럼 입력의 크기에 따른 소요 시간의 증가율이 적기 때문이다. 이진 탐색 트리에서 특정 값을 찾는 경우를 예로 들 수 있다.
선형 시간(linear time), O(n)
시간 복잡도가 O(n)인 경우이며, 입력에 따라 걸리는 시간이 선형적으로 증가함을 의미한다. 일차원 배열이나 링크드 리스트에서 특정 값을 찾는 경우를 예로 들 수 있다.
선형 로그 시간(linearithmic time), O(n logn)O(n^2)보다는 빠르지만, O(n)보다는 느리다. O(logn)의 시간이 걸리는 알고리즘의 n배의 시간이 걸린다고 할 수 있다. 이진 탐색 트리에서 노드의 삽입/제거는 O(logn)이 걸리는데, 데이터 삽입/제거 후 트리의 밸런스를 다시 잡는 자가 균형 이진 탐색 트리의 경우는 O(nlogn)이 걸린다.
다항 시간(quadratic time), O(n^2)
정수 n에 대한 선택 정렬 알고리즘이 상수 A에 대해서 An^2개의 연산을 수행한다. 그렇다면 이것은 O(n^2)의 시간동안 수행되며, 다항시간 알고리즘이라고 할 수 있다.
지수 시간(exponential time), O(2^n)
최악의 시간복잡도이다.
자료구조 별 시간 복잡도
Tree vs Sorted Array
일반적인 배열이 아니라 정렬된 배열의 경우 시간복잡도가 향상된다. 하지만 메모리 측면에서 트리가 효율이 좋은데, 그 이유는 배열은 메모리에서 연속적인 한 공간을 차지하는 반면에 트리는 링크드리스트를 이용하여 컴퓨터 메모리의 구석구석을 사용하기 때문이다. 그렇기 때문에 배열이 정렬된 상태일지라도 트리가 메모리 효율이 좀 더 좋다.
재귀 함수의 시간복잡도
반복문은 재귀 함수(Recursion)로 나타낼 수 있다.
분할-정복(divide-and-conquer) 문제
T(n)=T(divide)+T(conquer)+T(merge)
