시간복잡도 구하기

시간 복잡도란?

알고리즘을 평가할 때 시간 복잡도를 사용하곤 한다.

시간 복잡도는 최악의 경우에도 해당 알고리즘이 어떤 성능을 낼지 가늠해 볼 수 있기 때문에 주로 빅오 표기법을 사용한다.

 

알고리즘의 수행시간은 실행환경에 따라 다르게 측정되기 때문에 기본 연산의 실행 횟수로 수행시간을 평가한다.

기본 연산은

1. 데이터 입출력 - copy, move...

2. 산술 연산 - add, multiply...

3. 제어 연산 - if, while...

 

시간 복잡도는 최선의 경우, 최악의 경우, 평균적인 경우 세가지로 나타낸다.

평균적인 경우를 가장 많이 사용할 것 같지만 알고리즘이 복잡해질수록 평균적인 경우는 구하기가 매우 어려워지므로 주로 최악의 경우로 알고리즘의 성능을 파악한다.

 

시간 복잡도 계산

연산 횟수가 다항식으로 표현될 경우, 최고차항을 제외한 모든 항과 최고차항의 계수를 제외시켜 나타낸다.

예를 들어 입력 크가가 n이라고 할 때 다음과 같이 표기한다.

T(n)=n^2+2n+2=O(n^2) : 최고차항만 나타냄

T(n)=2n+2=O(n) : 최고차항의 계수는 제외함.

 

예를 들어 다음 알고리즘에서의 시간 복잡도는

int func (int n) {
  int sum = 0;     // 대입연산 1회
  int i = 0;       // 대입연산 1회
   
  for(i=0; i < n; i++) {  // 반복문 n+1회
    sum += i;             // 덧셈 연산 n회
  }
  for(i=0; i < n; i++) {  // 반복문 n+1회
    sum += i;             // 덧셈 연산 n회   
  }
  return sum;       // 리턴 1회
}

위 알고리즘에 단계별 연산 횟수는 주석과 같고 총 연산 횟수는 4n+5이다.

그러므로 이 알고리즘의 시간 복잡도는 T(n)=4n+5=O(n)이다.

 

시간 복잡도 표기

O(1) - 상수 시간(Constant time)

입력 크기(n)에 상관없이 일정한 연산을 수행하면 시간 복잡도는 O(1)이다.

void func (int n) {
  printf("%d\n", n);
}

위 알고리즘은 n에 상관없이 한 번의 연산만 수행하므로 시간 복잡도는 T(n)=O(1)이다.

 

O(logN)-로그 시간 (Logarithmic time)

입력 크기(N)가 커질 때 연산 횟수가 logN에 비례해서 증가하면 시간 복잡도는 O(logN)이다.

for(i=1; i<=n; i*2) {
  ...
}

위 알고리즘은 i값이 반복할 때마다 2배씩 증가한다. 이것을 k번 반복했을 때 다음과 같다.

2^k=N이 되고 반복문이 종료된다. 양쪽에 로그를 취하면 다음과 같다.

log2(2^k)=log2N

k=log2N

k는 수행횟수이기 때문에 시간 복잡도는 다음과 같다

T(n)=logN

 

O(n) - 선형 시간 (Linear time)

입력 크기(n)가 커질 때 연산 횟수가 n에 비례해서 증가하면 시간 복잡도는 O(n)이다.

for(i=0; i < n; i++) {
  ...
}

위 알고리즘은 n만큼 반복문을 수행한다.

n의 값에 비례하여 연산수가 션형적으로 증가하기 때문에 시간 복잡도는 T(n)=O(n)과 같다.

 

O(n^2) - 2차 시간 (Quadratic time)

입력 크기(n)가 커질 때 연산횟수가 n^2에 비례해서 증가하면 시간 복잡도는 O(n^2)이다.

for(i=0; i < n; i++) {
  for(j=0, j < n; j++) {
    ...
  }
}

위 알고리즘은 for문이 중첩되어 있기 때문에 n^2에 비례해서 연산수가 증가한다.

시간 복잡도는 T(n)=O(n^2)과 같다.

 

O(2^n) - 지수 시간(Exponential time)

입력크기가 커질 때 연산수가 2^n에 비례해서 증가하면 시간 복잡도는 O(2^n)이다.

int func (int n) {
  if (n <= 1) 
    return n;
  return func(n-1) + fun(n-2);
}

위 알고리즘은 피보나치 수를 구하는 알고리즘이다.

한번 함수를 호출할 때마다 두 번씩 재귀로 함수를 호출하기 때문에 2^n에 비례하여 연산수가 증가한다.

시간 복잡도는 T(n)=O(2^n)과 같다.

 

다음은 빅오표기법으로 표현한 알고리즘의 성능간 그래프이다.

 

출처

https://www.bigocheatsheet.com/

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(2n) < O(n!)

오른쪽으로 갈수록 시간 복잡도가 큰 알고리즘이다.

 n의 값이 작을 때는 알고리즘 사이에 큰 차이가 없지만 n의 값이 커지면 커질수록 복잡한 알고리즘은 수행 시간이 급격히 길어지게 된다.

시간 복잡도를 낮출 수 있다면 프로그램에 큰 성능 향상을 기대할 수 있다.

기본 연산 횟수 카운팅 예시

arrayMax(A, n)
  currentMax <- A[0] // 2 
  for i <- 1 to n-1 do // 2n 
    if A[i] > currentMax then // 2(n-1) 
      currentMax <- A[i] // 2(n-1)
  return currentMax // 1

 

currentMax <- A[0]

할당 연산(<-) 1번 + 인덱싱 연산(A[0]) 1번 = 2번

for i <- 1 to n-1 do 

[ 더하기 연산(i++) 1번 + 비교연산 (i < n-1) 1번 ] * [반복횟수 (n-1) ]  + 더하기 연산 1번 +  비교 연산 (i= n-1 일 때 1을 더해 i =n인 상태에서 n-1과 비교를 하고 i<n-1의 조건이 false가 나와 for문이 종료된다.)  1번 = 2 * (n-1) +2 = 2n번 
if A[i] > currentMax then

[ 인덱싱 연산(A[i]) 1번 + 비교 연산 ( > )1번 ] * [ 반복횟수 (n-1) ] = 2(n-1) 번
currentMax <- A[i] 

[ 인덱스 연산( A[i] ) 1번 + 할당 연산( <- ) 1번 ] * [반복횟수 (n-1) ] = 2(n-1) 번
return currentMax // 1

리턴 연산 1번

 

따라서 총 연산이 6n -1번 진행되며 시간 복잡도는 O(n)으로 표기 할 수 있다.

 

: https://yoongrammer.tistory.com/79