시간 복잡도 구하는 법

시간 복잡도란?

위키피디아에 나온 시간 복잡도 내용을 인용하자면,
기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량과 알고리즘에 의해 수행되는 기본적인 연산의 개수는 최대 상수 인자만큼 다르다.

시간 복잡도 종류

• O(Big-O): 최악의 시간 복잡도
• Ω(Omega): 최선의 시간 복잡도
• Θ(Theta): 평균 정도의 시간 복잡도

여기서 우리가 흔히 말하는 "이 코드의 시간 복잡도는 얼마에요?" 라는 물음에 답을 할 때는 Big-O(빅오) 표기법을 사용한 시간 복잡도를 말한다.

왜냐, Big-O 표기법은 최악의 경우를 고려하는 것이므로 프로그램 실행 과정 중 최악의 시간까지 미리 생각해 볼 수 있기 때문이다.

예시

// 1번 코드
int sum = 0;
for(int i = 0; i<n; i++){
	sum+=i;
}

1번 코드는 'sum=0' 한 번, 'int i = 0'이 한 번, 'i++'이 n번,'sum+=i'가 n번 합쳐서 총 2n+2번의 연산이 수행된다.
Big-O 표기법에서는 최대 차항만 계수없이 표기하기 때문에 O(N)이 된다.

// 2번 코드
int sum = (x+1)*x/2;

2번 코드 같은 경우 '(x+1)'이 한 번, '*x'가 한 번, '/2'가 한 번 계산된 값을 sum에 대입할 때 한 번 이렇게 총 네 번이므로 4가 되지만, Big-O 표기법으로는 O(1)이 된다.

// 3번 코드
int sum = 0;
for(int i = 0; i<n; i++){
	for(int j = 0; j<i;j++){
    	sum+=j;
    }
}

3번 코드의 바깥쪽 반복문은 n번, 안쪽 반복문은 i의 값에 따라 반복합니다.
i는 0부터 n-1까지 변하고, 안쪽 반복문은 해당하는 i만큼 반복하므로 0+1+2+...+(n-1) = n*(n-1)/2번(등차수열의 합 공식) 반복합니다.
이 역시 최대 차항만 계수없이 표기하게되면 O(n²)이 됩니다.

// 4번 코드
int sum = 0;
for(int i = n; i>0; i/=2){
	for(int j = 0; j<i; j++){
    	sum+=j;
    }
}

4번 코드는 바깥쪽 반복문이 logN번 반복, 안쪽 반복문은 i값에 따라 반복 횟수가 달라집니다.
(💡 logN번 반복인 이유는 i/=2이기 때문)
i는 n부터 1까지 변하고, 안쪽 반복문은 해당하는 i만큼 반복하므로 n+(n/2)+(n/4)+..+1 = 2n번 반복하므로 O(N)이 됩니다.

정리

즉 Big-O 표기법을 간단하게 정리하면
1) 연산의 개수를 세어본다.
2) 가장 높은 차수만 남긴다. ex) O(n²+n) => O(n²)
3) 계수 및 상수는 과감하게 버린다. ex) O(2n+3) => O(n)