시간의 복잡도-빅오(Big-O)1

빅오 (Big-O)1

알고리즘은 궁극적으로 컴퓨터로 구현되므로, 컴퓨터의 빠른 처리 능력을 감안하면 아무리 복잡한 알고리즘도 입력의 크기가 작으면 금방 끝나버린다. 그러므로 관심의 대상이 되는 것은 입력의 크기가 충분히 클 때다. 충분히 큰 입력에서는 알고리즘의 효율성에 따라 수행 시간이 크게 차이가 날 수 있기 때문이다.

 

파일 크기에 따른 소요시간

간단한 예를 들어보자. 디스크에 저장된 파일을 다른 지역에 살고 있는 친구에게 보낸다고 가정해보자 여기서 교통비 드 물리적인 비용은 전혀 고려하지 않고 단순히 시간만 따진다고 해보자. 이때 파일 크기가 작다면, 즉 n이 작다면 O(n)의 시간이 걸리는 온라인 전송이 빠르다. 하지만 파일이 아주 크다면 비행기를 통해 물리적으로 배달하는 게 더 빠를 수 있다. 파일이 아무리 커도, 즉 n이 아무리 커도 비행기를 통한 파일 전송은 O(1)로 항상 일정한 시간이 소요되기 때문이다. 이 것이 점근적 실행 시간에 대한 개념이며, 빅오는 이런 점근적 실행 시간을 표기하는 방법중 하나이다.

 

점근적 실행 시간을 달리 말하면 시간 복잡도(Time Complexity)라고 할수 있다. 이런 복잡도를 표기하는 대표적인 방법이 바로 빅오이다. 빅오로 시간 복잡도를 표현할 때는 최고차 항만은 표기하며, 계수는 무시한다. 예를 들어 입력값 n에 대해 4n² + 3n + 4번 만큼 계산하는 함수가 있다면  이 함수의 시간 복잡도는 최고차 항인 4n²만을 고려한다. 이 중에서도 계수는 무시하며 n²만을 고려한다. 즉 여기서 시간의 복잡도는 O(n²)이 된다.이 처럼 시간 복잡도를 표기할 때는 구체적인 연산 횟수가 아니라 입력값에 따른 알고리즘 실행 시간의 추이만을 살피게 된다. 어차피 연산 횟수가 같다고 해도 어떤 연산이냐에 따라 실행 속도는 천차만별이며, 컴퓨터 과학에서는 구체적인 실행 속도보다는 실행시간의 추이에 좀 더 비중을 두기 때문이다.  

 

• O(1) : 입력값이 아무리 커도 실행 시간이 일정하다. 예를 들어, 다음과 같이 상수를 리턴하는 함수를 살펴 보자

 

public int fn(int n){
    return 42;
}

 

위 코드의 함수는 n의 크기가 얼마든 간에 항상 같은 상수를 반환하므로 O(1)이다. 크기에 전혀 영향을 받지 않기 때문에 궁극적 알고리즘이라고 할 수 있다. 하지만 상수 시간에 실행된다 해도 상수값이 상상을 넘어설 정도로 매우 크다면 사실상 시간이 일정한 것에 의미가 없다.  O(1)에 실행되는 알고리즘의 예로는 배열에서 값을 조회할 때, 연결리스트의 끔에 값을 삽입할 때, 해시 테이블의 조회 및 삽입 등이 있다.

 

• O(log n) : 여기서부터 실행 시간은 입력값에 영향을 반는다. 다음은 입력값을 반으로 나누는 함수다.

 

public int fn(int n){
    while(n > 1)
    	n /=2;
    return n;
}

 

위 코드의 함수는 n의 값을 계속해서 반으로 나누는데, 연산 횟수가 log₂ n의 결과와 동일하다. 컴퓨터 과학에서는 주로 밑이 2를 생략하여 log n으로 표현한다. 직접 계산해보면 알겠지만 로그는 매우 큰 입력값에도 크게 영향을 받지 않는다. 웬만한 크기의 n에 대해서도 매우 견고하다. 사실상 O(log n) 정도면 최고의 알고리즘 이라고 할 수 있다. 대표적으로 이진 검색(Binary Search)이 이에 해당한다.

 

• O(n) : 정확히 입력값(n)의 크기만큼 실행 시간에 영향을 받으며, 알고리즘을 수행하는데 걸리는 시간은 입력값에 비례한다. 다음은 입력값만큼 연산하는 함수다.

 

public int fn(int n){
   int r = 0;
   for(int i = 0; i < n; i++ ){
       r++;
   }
   return r;
}

 

이 함수는 정확히 n의 크기만큼 연산을 진행한다. 실행 시간이 선형(Linear)으로 증가하기 때무에 O(n)알고리즘을 선형 시간(Linear-Time)알고리즘이라고도 한다. 정렬되지 않은 리스트에서 최댓값 또는 최솟값을 찾는 경우가 이에 해당하며, 이 값을 찾기 위해서는 모든 입력값을 적어도 한 번은 살펴봐야 하므로 정확히 O(n)이 된다.

 

• O(n log n) : 입력값 만큼 순회하면서 log n의 연산이 곱해진다. 다음은 입력값만큼 순화하면서 각 순서에 해당하는 값을 반으로 나눠가면 연산하는 함수다.

 

public int fn(int n){
  int r = n;
  for(int i = 0 ; i < n; i++){
  	while(n >1)
    	n /=2;
      n = r;
  }
  return r;
}

 

이 함수는 입력값 n의 크기만큼 순회하면서, 다시 입력값을 반으로 나눠가며 log n의 연산을 진행한다. 병합 정렬 Merge Sort을 비롯한 효율적인 정렬 알고리즘이 이에 해당한다. 적어도 모든 수에 대해 한번 이상은 비교해야 하는 비교 기반 정렬 알고리즘은 아무리 좋은 알고리즘도 O(n log n)보다 빠를 수 없다. 물론 입력값이 최선이 경우, 비교를 건너뛰는 최적화를 추가하면 O(n)이 될 수 있으며 파이썬의 기본 정렬 알고리즘인 팀소트Timsort가 이런 로직을 갖고 있다. 하지만 기본적으로 모든 정렬 알고리즘은 최악의 경우 O(n log n)보다 빠를 수 없다. 이 외에도 O(n log n)은 특별한 의미가 있다. 좋은 알고리즘이라 친하는 대부분이 이 범주에 들기 때문이다. 로그의 마법과 같은 특징 때문에 log n은 좀처럼 큰 수가 나오지 않는다. 실용적인 관점에서 O(n)이나 O(n log n)은 사실상 비슷한 성능으로 가정해도 무방하다.

 

 

• O(n² ) : 입력값의 제곱만큼 연산하다. 다음은 입력값을 중첩으로 반복하면서 연산하는 함수이다.

public int fn(int n){
   int r = 0;
   for(int i = 0; i < n; i ++){
     for(int j = 0; j < n; j++){
         r+=j;
     }
   }
   return r;
}

 

이 함수는 n크기 만큼 다시 n번 연산을 진핸한다. 버블 정렬 Bubble Sort같은 비효율적인 정렬 알고리즘이 이에 해당한다. 이제 여기서부터는 신중하게 살펴봐야 한다. 왜냐하면 입력값이 클 경우 n²부터는 타임아웃이 발생하는 경우가 잦기 때문이다. 이 때무에 코딩 테스트에서 알고리즘을 최적화한다고 하면  O(n²)을 O(n log n)으로 줄이는 일이 거의 대부분이다. 

 

 

• O(2ⁿ): 입력값의 크기만큼 2배씩 연산한다.  다음은 피보나치Fibonacci수를 재귀로 계산하는 알고리즘을 구현한 함수다.

public int fn(int n){
    if( n <= 1)
        return n;
    else
    	return fn(n -1) + fn(n -2);
}

 

이 함수는 2ⁿ번 만큼 연산을 진행한다. 정확히는 1.6 정도 되지만 피보나치 수를 얘기할 대는 단순하게 2ⁿ으로 언급해도 충분하다. 간속 n²과 혼동하는 경우가 있는데, 비슷해 보지이만 2ⁿ 쪽이 훨씬 크다.

 

• O(n!) : 입력값을 1씩 줄여가며 곱셈 연산을 한다. 다음은 입력값의 크기만큼 순회하면서, 다시 입력값을 1씩 줄여가며 재귀 호출하는 함수이다.

 

public int fn(int n){
   for(int i = 0; i < n; i++)
     fn(n-1);
   retutn n;
}

 

이 함수는 여러번 재귀 호출을 한다. 실제로는 fn() 함수 호출을 모두 합하면 약 2.7 x n! 만큼 호출하는데, 여기서 상수 항을 제외하면 시간 복잡도는 O(n!)이다. O(n!)은 가장 느린 알고리즘으로, 입력값이 조금만 커져도 웬만한 다항 시간 내에 계산이 어렵다. 

 

빅오 표기법에 따른 시간 복잡도

 

O(1)    <

O(log n)    <

O(n)    <

O(n log n)  <

O(n²)    <

O(2²)    <

O(n!)

상수시간

로그시간

선형시간

선형로그시간

이차시간

지수시간

팩토리얼시간

 

 

n² 과 2ⁿ의 비교

n=1	n²=1	2ⁿ=2
n=2	n²=4	2ⁿ=4
n=3	n²=9	2ⁿ=8
n=4	n²=16	2ⁿ=16
n=5	n²=25	2ⁿ=32
n=6	n²=36	2ⁿ=64
n=7	n²=49	2ⁿ=128
n=8	n²=64	2ⁿ=256
n=9	n²=81	2ⁿ=512
n=10	n²=100	2ⁿ=1024
n=11	n²=121	2ⁿ=2048
n=12	n²=144	2ⁿ=4096
n=13	n²=169	2ⁿ=8192
n=14	n²=196	2ⁿ=16384
n=15	n²=225	2ⁿ=32768

 

일반적으로 재귀 알고리즘은 실행하는데 O(2ⁿ)의 시간이 걸리는 비효율적인 알고리즘이다. 그러나 메모이제이션Memoization같은 최적화를 적용하면 실행 시간을 O(n)까지 줄일 수 있다.