알고리즘 복잡도와 빅 오 표기법

알고리즘의 복잡도

알고리즘 문제를 풀다보면 작성한 코드의 복잡도가 얼마인지 명시해야할 때가 있다. 복잡도에는 시간 복잡도와 공간 복잡도가 있다. 요즘에는 공간 복잡도에 대한 중요성은 떨어지고 있어 일반적으로 알고리즘에서 복잡도라고하면 시간 복잡도를 의미한다.

 

시간 복잡도

함수인 알고리즘을 특정 크기의 input을 받아 실행할 때 걸리는 시간의 양을 의미한다.

 

공간 복잡도

함수인 알고리즘을 특정 크기의 input을 받아 살행할 때 필요한 메모리의 양을 의미한다.

 

빅 오 표기법 (Big O Notation)

알고리즘에서 빅 오 표기법이란 input의 크기 n이 증가할 때 시간 복잡도 또는 공간 복잡도가 어떻게 증가하는지 구분하기 위해 사용하는 표기법이다. 엄밀한 정의는 수학적이라 알 필요는 없을 듯하다. 알고리즘 코드를 작성하는 관점에서는 input의 크기 n이 증가할 때 연산 수가 어떤 형태로 증가하는지 파악하고 명시하면된다. 

 

O(1) 복잡도

input의 크기 n이 커질 때 연산수가 증가하지 않고 일정하면 시간 복잡도를 O(1)로 표기한다. 예시는 다음과 같다.

function func (input){
  return input[0];
}

이 경우는 input의 크기에 관계없이 연산수는 1이다. 따라서 시간 복잡도는 O(1)이다.

 

O(n) 복잡도

input의 크기 n이 커질 때 연산수가 n에 비례해서 증가하면 시간 복잡도를 O(n)으로 표기한다. 예시는 다음과 같다.

function func (input){
  let output = 0;
  for (let i=0; i<input.length; i++){ 
    output += input[i];
  }
  return output;
}

이 경우 input의 크기 n에 따른 연산수는 n이다. 따라서 시간 복잡도는 O(n)이다. 만약 같은 연산을 두번하는 코드를 작성했다면 시간 복잡도를 어떻게 표기할까?

function func (input){
  let output = 0;
  for (let i=0; i<input.length; i++){ 
    output += input[i];
  }
  for (let i=0; i<input.length; i++){ 
    output += input[i];
  }
  return output;
}

이 경우 연산수는 2n이 되지만 빅 오 표기법에서는 상수는 제외하고 표기하기 때문에 O(2n)이 아니라 O(n)으로 시간 복잡도를 표기한다.

 

O(n^2) 복잡도

input의 크기 n이 커질 때 연산수가 n^2에 비례해서 증가하면 시간 복잡도를 O(n^2)으로 표기한다. 예시는 다음과 같다.

function func (input){
  let output = 0;
  for (let i=0; i<input.length; i++){ 
    for (let j=0; j<input.length; j++){ 
      output += input[i];
    }
  }
  return output;
}

이 경우 input의 크기 n에 따른 연산수는 n^2이다. 따라서 시간 복잡도는 O(n^2)이다. 코드에 시간 복잡도가 O(n)인 연산이 섞여 있더라도 O(n^2)로 표기한다. 빅 오 표기법에서는 가장 연산수가 큰 복잡도를 따라 표기한다. 만약 반복문이 세 번있었다면 시간 복잡도는 O(n^3)이 된다.

 

O(log n) 복잡도

input의 크기 n이 커질 때 연산수가 logn에 비례해서 증가하면 시간 복잡도를 O(log n)으로 표기한다. 예시는 다음과 같다.

function func (num, arr,sIdx,eIdx){
  if (sIdx > eIdx){
    return -1;
  }
  let idx = parseInt((sIdx + eIdx)/2);
  if (arr[idx] === num){
    return idx;
  }else if (arr[idx] > num){
    return func(num, arr, sIdx,idx-1);
  }else{
    return func(num, arr, idx+1, eIdx);
  }
}

O(log n) 복잡도를 가지는 대표적인 예시인 오름차순 정렬된 배열의 이진 검색이다. 오름차순으로 정렬된 배열인 input에서 숫자 num이 어디 있는지 검색할 때 이진 검색을 이용할 수 있다.

 

이진 검색은 전체 크기 n의 절반인 n/2 번째 배열의 요소와 num을 비교하고 그 요소가 num보다 크면 0부터 n/2 번째 배열의 중간과 비교하고, 작으면 n/2부터 n 번째 배열의 중간과 비교하며 num이 나올 때까지 검색하는 알고리즘이다. 이 경우 N을 k번 2로 나누어 1이 될때까지 실행하여 2^k = N, k = log2 N이 성립한다. 즉 log2 N번 연산하므로 시간 복잡도는 O(log n)이 된다.

 

O(2^n) 복잡도

input의 크기 n이 커질때 연산수가 2^n에 비례해서 증가하면 시간 복잡도를 O(2^n)으로 표기한다. 예시는 다음과 같다.

function func (num){
  if(num <= 1){
    return num;
  }else{
    return func(num-1) + func(num-2);
  }
}

O(2^n) 복잡도를 가지는 대표적인 예시인 피보나치 수를 구하는 알고리즘이다. n 번째 피보나치 수를 구하기 위해서는 n-1, n-2 번째 피보나치를 수를 구해야하므로 1+2+4+8+2^(n-1) 번 연산을 해야한다. 총 2^n-1번 연산을하여 시간 복잡도는 O(2^n)이 된다.

 

복잡도 비교

O(1) < O(log n) < O(n) < O (n^2) < (n^3)< O(2^n)