[알고리즘 이론] 시간 복잡도

알고리즘의 시간 복잡도

 

 

시간 복잡도란 무엇일까?

시간 복잡도는 입력의 크기를 통하여 알고리즘의 수행 시간을 추정 값이다. 이를 통하여 알고리즘을 구현하기 전, 해당 방법으로 구현하였을 때의 수행 속도를 예상할 수 있다. 

 

시간 복잡도 표현 방법

시간 복잡도는 'O(...)'로 나타낸다. 괄호 안에는 함수가 들어간다. 한번 예제를 통하여 알아보자.

 

예시01)

a++;

b++;

c = a + b;

O(1) : 위와 같이 코드가 단일 명령어로 구성되어 있었을 때의 시간 복잡도이다. 

---

예시02)

for (int k = i+1; k < v.size()-1; k++) {
    for (int j = k + 1; j < v.size(); j++) {

}

}

O(n^2) : 위와 같이 코드가 단일 명령어로 구성되어 있었을 때의 시간 복잡도이다. 

---

위의 예시에서 눈치 챘겠지만, 시간 복잡도는 반복문 내부 코드의 수행 횟수를 정확하게 표현하지 않는다. 즉, 상수인자는 무시된다. 

 

 

 

자주 활용되는 시간 복잡도?

O(1)	상수시간 알고리즘으로 수행시간은 입력의 크기에 영향을 받지 않는다.
O(log n)	로그 시간 알고리즘이다. 단계마다 입력의 크기를 절반씩 줄여 나간다.
O(n)	선형 시간 알고리즘이다. 입력을 살펴보는 과정을 상수 번 수행한다. 대부분의 경우 선형 시간이 가장 효율적인 시간 복잡도이다.
O(n log n)	이는 입력을 정렬하는 과정의 시간 복잡도로 많이 활용한다.
O(n^2)	제곱시간 알고리즘은 2중 중첩된 반복문을 사용할 경우에 해당된다. 해당 시간안에 입력 원소 두개로 만들 수 있는 모든 조합을 한번씩 살펴 볼 수 있다.
O(2^n)	입력 원소로 만들 수 있는 모든 부분집합을 한번씩 살펴보는 알고리즘을 나타낼 때 자주 사용한다.
O(n!)	입력 원소로 만들 수 있는 모든 순열을 한 번씩 살펴보는 알고리즘의 시간복잡도이다.