소스 코드의 실행시간은 실행환경의 영향을 많이 받기 때문에 실제로(Real-time 환경 제외) 시간복잡도(Time Complexity)를 측정할 때는 해당하는 알고리즘에 포함된 연산의 실행 횟수가 기준이 되어 카운트 된다.
bubble sort 알고리즘의 경우 비교 연산이 들어가는데 입력되는 데이터의 크기에 따라서 비교 연산의 횟수가 바뀌게 된다. 데이터의 크기가 2로 주어진다면 비교 연산은 1번 수행이 되겠지만 데이터의 크기가 n개인 경우, 내가 찾는 값이 배열의 맨 끝에 위치해 있다고 가정했을 때 (n-1)번 연산이 수행 되는 경우도 고려할 수 있다.
이 처럼, 최소한의 실행 횟수로 알고리즘을 수행하는 경우를 Best Case라고 부르고 가장 많은 실행 횟수 끝에 알고리즘을 수행하는 경우를 Worst Case라고 부른다.
그렇다면 실제로 연산 횟수에 카운트 되는 연산은 어떤 것들이 있을까?
시간복잡도 추정에 인정되는 연산
- 변수에 값을 선언하는 경우
- 함수 호출
- 산술 연산
- 비교 연산
- 배열의 인덱싱을 사용한 코드
- 반환 (return)
- 참조 or 함수 내부 property 접근
점근적 분석 표기법 (Asymptotic analysis)
어떤 알고리즘의 연산 수행 시간이 n(n-1)/2 + 5 라는 구체적인 값으로 나왔을 때, 데이터 growth rate에 영향을 줄 수 있는 표기를 사용한다. 위의 연산 수행시간의 경우, growth rate에 영향을 줄 수 있는 것은 최고차항의 차수이기 때문에 빅-오 표기법을 간단히 O(n^2)으로 축약해서 서술한다.
아래의 코드를 보자.
int sample(int data[], int n)
{
int k = n/2;
return data[k];
}n개의 데이터가 저장된 배열 data[]가 주어지고 그 중 n/2번째 데이터를 반환하는 코드이다. 이 경우에 시간복잡도는 어떻게 될까? 데이터의 갯수는 n개로 주어져 있지만, 위의 코드 블록에서 실행하는 연산의 횟수는 각각 1번으로 count 되기 때문에 실제 시간복잡도는 O(1)이다. 데이터의 갯수도 중요하지만 수행하는 알고리즘의 영향을 받는다는 것을 알 수 있다.
다음의 코드를 보자.
def sequencial_search(a, k):
n = len(a)
for i in range(0, n):
if k == a[i]:
return i
return -1위의 알고리즘으로 원하는 값을 찾는 경우, 시간복잡도는 어떻게 될까? 경우를 두 가지로 나눠 볼 수 있다.
- 찾으려는 값이 list 안에 존재하는 경우
Best Case : O(1)
Worst Case : O(n)
- 찾으려는 값이 list 안에 존재하지 않는 경우
Best case : O(n)
# list 안에 값이 존재하지 않기 때문에
# 결국 n번 비교하게 되는 worst case와 같아질 수 밖에 없다.
Worst case : O(n)시간복잡도의 점근적 표기법(big-O표기, omega표기) 모두 데이터의 갯수가 양수인 상황을 다룬다. 무수한 데이터를 어떻게(how to) 다룰 것인가의 질문을 돌려서 말하는 것이기도 하다.
(사진 출처: google)
f(n) = n(n-1)/2 + 5 인 경우, g(n) = n^2은 서로 같지는 않지만, g(n)의 증가 속도와 비슷하게 증가하는 경향을 보인다.
lower bound 에서의 시간 복잡도 개념은 상당히 많이 쓰이는데, 그 이유는 최적의 시간복잡도를 찾는 알고리즘을 설계하기 위해서 이다.
가령 linear search의 경우, 키가 일치하지 않으면 첫 번째 요소와 키를 비교하고 두 번째 요소와 비교하는 식으로 n 번째 요소에 대해 확인할 때까지 계속 알고리즘을 수행하지만 binary search 에서는 키에 대해 중간 요소를 확인하고 키의 값이 더 크면 전반부를 검색하고 나머지 절반을 확인하고 동일한 프로세스를 반복한다.
lower bound를 통해 두 경우의 최대 비교 횟수, 최대로 검색할 수 있는 노드의 수를 추정할 수 있다.
upper bound, lower bound의 개념으로부터 연산 횟수에 따른 시간 복잡도를 추정할 수 있고 그로부터 알고리즘의 average case 및 worst case의 시간 복잡도 또한 추정할 수 있다.
