시간복잡도에 대해

시간복잡도(time complexity)

- 알고리즘의 자원(resource) 사용량을 분석한다.

- 자원이란 실행 시간, 메모리, 저장 장치, 통신 등을 의미한다.

- 실행시간은 실행 환경에 따라 달라진다.(하드웨어, 운영체제, 언어, 컴파일러 등)

- 실행 시간을 측정하는 대신에 연산의 실행 횟수를 센다.

- 데이터의 크기가 같아도 실제 데이터에 따라 시간 복잡도는 달라질 수 있다.

최악 시간 복잡도(worst-case analysis)

평균 시간복잡도(average-case analysis)

점근적 분석

- 점근적 표기법을 사용한다.

데이터 개수가 n -> ∞일 때 수행시간이 증가하는 growth rate로 시간복잡도를 표현하는 기법이다.

주로 세타(Θ) 표기, 빅오(O) 표기법을 사용한다.

- 점근적 분석 기법은 유일한 분석법도 아니며 또한 가장 유용한 분석법도 아니다. 그럼에도 많은 빈도로 쓰이는 이유로는 상대적으로 가장 간단하고 알고리즘의 실행환경에 의존적이지 않기 때문이다.

EX1 : 상수 시간 복잡도

int sample (int data[], int n) {

int k = n / 2;

return data[k];

}

-> n에 관계없이 상수 시간이 소요되며, 알고리즘의 시간 복잡도는 O(1)이 된다.

EX2 : 선형 시간복잡도

int sum (int data[], int n) {

int sum = 0;

for (int i = 0; i < n; i++)

sum = sum + data[i];

return sum;

}

- sum = sum + data[i];는 위의 예시에서 가장 자주 실행되는 문장이며 실행 횟수는 항상 n번이다.

- 가장 자주 실행되는 문장의 실행횟수가 n번이라면 모든 문장 실행 횟수의 합은 n에 선형적으로 비례하고 모든 연산들 실행횟수의 합도 n에 역시 비례하게 된다.

-> 선형 시간복잡도를 가진다고 표현하며 이 때 시간 복잡도는O(n)이 된다.

EX3 : 선형 시간복잡도 - 순차탐색

int search (int n, int data[], int target) {

for (int i = 0; i < n; i++)

if (data[i] == target)

return i;

return -1;

}

- if (data[i] == target)은 위 예시에서 가장 자주 실행되는 문장이며 탐색하고자 하는 데이터가 가장 뒤에 있을 최악의 경우 실행횟수는 n번이 된다.

-> 시간 복잡도는 O(n)이라고 표기한다.

Quadratic

bool is_distinct(int n, int x[]) {

for (int i = 0; i < n - 1; i++)

for (int j = i + 1; j < n; j++)

if (x[i] == x[j])

return false;

return true;

}

- if (x[i] == x[j])는 위 예시에서 가장 자주 실행되는 문장이며, 최악의 경우 실행횟수가 n(n - 1) / 2번이 된다.

-> 최악의 경우 배열에 저장된 모든 원소 쌍을 비교하게 되어 비교 연산의 횟수는 n(n - 1) / 2이다.

해당 시간 복잡도는 최종적으로 O(n^2)으로 나타낸다.

점근적 표기법

- 알고리즘에 포함된 연산들의 실행 횟수를 표기하는 하나의 기법이다.

- 최고차항의 차수만으로 표시하게 된다.

- 가장 자주 실행되는 연산이나 문장의 실행횟수를 고려하는 것만으로 시간 복잡도를 구할 수 있다.

O - 표기 (빅오 표기)

Ω - 표기 (옴 표기)

Θ - 표기 (세타 표기)

점근 표기법

빅오표기법의 복잡도 순서

- O(1) = Constant

상수형 빅오, 데이터의 양과 상관없이 항상 일정한 실행 시간을 가진다.

ex) 해쉬검색 알고리즘

- O($log n$) = Logarithmic

로그형 빅오, 데이터 양이 많아져도 증가율에 비해 연산횟수의 증가율이 훨씬 낮다

ex) 분류 및 정렬 (이진 검색, 퀵 정렬, 병합 졍렬)

- O($n$) = Linear

선형 빅오, 데이터 양에 따라 정비례한 시간 증가를 보인다.

ex) 선형탐색, 단일 반복문

- O($n log n$) = Log - Linear

선형 로그형 빅오, 데이터 양이 N배 많아지면 실행 시간은 N배보다 조금 더 많아진다. (정비례하지 않다.)

ex) 분류 및 정렬 후 다시 하나로 모을 때, 이진 트리 검색시 로직에 반복문을 덮어씌울 때

- O($n^2$) = Quadratic

데이터 양에 대해 걸리는 시간은 제곱에 비례한다.

ex) 이중 반복문, 삽입정렬, 선택정렬, 버블정렬

- O($n^3$) = Cubic

데이터 양에 대해 걸리는 시간은 세제곱에 비례한다.

ex) 삼중 반복문

- O($2^n$) = Exponential

지수형 빅오, 지수적 증가라는 엄청난 크기의 연산횟수 증가를 보인다. 사용 자체가 비현실적인 편이다.

- O($n!$) = Factorial

팩토리얼 빅오, 지수보다 더한 크기로 증가하여 사실상 이정도까지 시간이 걸리는 것이 힘든 수준이다.

- 상수형부터 지수형까지 순서대로 내려올수록 속도가 느려진다.

빅오 표기법의 시간 복잡도 그래프

빅오 표기법 시간 복잡도표

다항시간(polynomial-time) 알고리즘

- 알고리즘들은 실행 시간이 다항식일 때 효율적이라 할 수 있다.

이진 검색(Binary Search) 알고리즘

- 배열에 데이터들이 오름차순으로 정렬되어 저장된 상태이다.

- 데이터가 연결리스트에 오름차순으로 정렬되어 있다면

연결리스트에서는 가운데 데이터를 O(1)시간에 읽을 수가 없다.

따라서 이진검색을 수행하는 것이 불가능해진다.

- 이진 검색 구현

int binarySearch(int n, char *data[], char *target) {

int begin = 0, end = n - 1;

while (begin <= end) {

int middle = (begin + end) / 2;

int result = strcmp(data[middle], target);

if (result == 0)

return middle;

else if (result < 0)

begin = middle + 1;

else

end = middle - 1;

}

return -1;

}

-> 한 번 비교할 때마다 데이터가 절반씩 줄어들게 된다. 결과적으로 시간 복잡도는 O($log_{2}n$)이 된다.