시간복잡도
컴퓨터 프로그램의 입력값과 연산 수행시간의 상관관계를 나타내는 척도입니다. 다른 의미로는 알고리즘을 수행하기 위해 프로세스가 수행하는 연산을 수치화 한 것입니다. 일반적으로 점근 표기법을 이용하여 나타냅니다.
점근 표기법(Big-O)
알고리즘의 시간복잡도를 나타내는데 사용됩니다. 이걸 쓰는 이유는 성장률(입력값의 크기에 따른 함수의 증가량)에서 중요하지 않은 상수들을 제거하면 알고리즘의 실행시간에서 중요한 의미를 갖는 성장률에만 집중 할 수 있기 때문입니다. 또, 프로그램이 돌아가는 정확한 단계의 수를 결정하는 작업은 매우 어렵기 떄문입니다.
예를들어, $x = y$ 와, $x = y + z * (x/y)$ 는 프로그램에서 같은 단계로 간주하고, 이를 구분하는것은 어렵습니다.
그런데 입력 데이터 개수 n에 대해 두 프로그램의 차이가 $5n+7$과 $n^2+25$와 같이 차수의 차이가 나는 경우 비교의 가치가 있게 됩니다.
여기에서 점근적 표기법은 실질적으로 값의 크기에 비례하는 n과 n^2에 집중하여 점근적 실행 시간을 표기하는 방법입니다.
결국, $O(5n+7)=O(5n)=O(n)$이 되고, $O(n^2+25)=O(n^2)$이 된다는 뜻입니다.
시간복잡도의 단계
시간복잡도와 로직의 수행시간은 비례합니다. 그러므로 시간 복잡도 수치가 작을수록 효율적인 성능의 알고리즘을 뜻합니다. big-o에서 가장 중요하게 보는 것은 최고차항 n의 단위(최고차항 아래는 무시)이고, $log n$의 경우 $log_2 n$을 뜻합니다.
- 아래로 갈수록
- $O(1)$과 같은 상수(constant) 형태(상수 시간) : 문제를 해결하는데 오직 한 단계만 처리함.
- $O(log n)$과 같은 로그(logarithmic) 형태(로그 시간) : 문제를 해결하는데 필요한 단계들이 특정 요인에 의해 줄어듦. 이진 탐색
- $O(n)$과 같은 선형(직선적 시간) : 문제를 해결하는데 필요한 단계 수와 입력값의 개수 n이 1:1 관계를 가짐.
- $O(n log n)$ 과 같은 선형로그 형태 : 퀵 정렬, 병합 정렬, 힙 정렬은 이런 시간 복잡도를 지닙니다.
- $O(n^c)$과 같은 다차(polynomial) 형태 : c중 for문을 이용한 정렬
- $O(c^n)$과 같은 지수(exponential) 형태 : 메모아이제이션을 하지 않은 재귀 함수.
- $O(n!)$과 같은 형태
댓글남기기