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

빅오 (Big-O)

빅오를 계산하는 실용적인 방법

한눈에 빅오를 계산할 수 있으면 가장 좋지만 사실 웬만큼 알고리즘에 익숙하더라도 헷갈릴 때가 많다. 팩토리얼(n!) 계산 같은 게 그런 예다. 다음은 팩토리얼을 재귀로 구현한 코드이다.

public int factorial(int n){
    if( n>= 1){
       return n * factorial(n-1);
    }else{
      return 1;
    }
}

 

얼핏 봐서는 팩토리얼 계산이고 재귀도 있고 하니 시간 복잡도는 O(n!) 쯤 될거 같다. 하지만 자세히 살펴보면 재귀는 n, n-1, n - 2, ... 순으로 한 번씩만 구하면 되기 때문에 시간의 복잡도는 O(n)에 불과하다. 자칫 헷갈리기 쉬운 부분이다. 그렇다면 어떻게 하면 정확하게 계산할 수 있을까? 다음과 같이 함수를 리턴으로 종료하기 직전에 연산 횟수를 헤아려보자

 

public int factorial(int n){
    if( n>= 1){
       count++;
       return n * factorial(n-1);
    }else{
       count++;
       return 1;
    }
}

 

이처럼 연산 횟수를 직접 헤아리는 방법이 가장 쉬운 방법이다. 몇 번 이나 연산했습니다 count변수로 일일이 연산 횟수를 헤아려보면 정확하게 알 수 있다.

 

factorial(5), count=6
factorial(6), count=7
factorial(7), count=8

 

출력 결과를 보면 시간 복잡도는 정확히 O(n+1)이고, 여기서 상수는 생략하면 O(n)임을 알 수 있다.  이처럼 연산 횟수를 직접 헤아리는 방법은 코딩 테스트나 실무에서도 쓸 수 있는 실용적인 방법이며, 또한 정확하게 계산할 수 있어 매우 유용하다.

 

상한과 최악

빅오(O)는 상한 Upper Bound을 의미한다. 이 외에도 하한 Lower Bound을 나타내는 빅오메가(Ω), 평균을 의미하는 빅세타(ϴ)가 있는데, 학계와 달리 업계에서는 빅세타와 빅오를 하나로 합쳐서 단순화해 표현하려는 경향이있다. 

 

주의할 점은 상한을 최악의 경우와 혼동하는 것인데, 빅오 표기법은 정확하게 쓰기에는 너무 길고 복잡한 함수를 '적당히 정확하게' 표현하는 방법일 뿐, 최악의 경우/평균적인 경우의 시간 복잡도와는 아무런 관계가 없는 개념이라는 점에 유의해 야한다. 

 

좀 더 구체적으로 퀵 정렬Quick Sort을 예로 들어 보자 입력값이 [1, 4, 3, 7, 8, 6, 5]일 때  퀼 정렬의 로무토 파티션Lomuto Partition(로무토 파티션은 피벗을 정할 대 가장 우측을 택하는 가장 단순한 피벗 선택 방식이다.) 해당 입력값은 총 18번의 비교 또는 스왑 연산이 필요하다. 이 경우가 최선의 경우에 해당하며 O(n log n)에 가깝다. 여기서 엘리먼트는 7개 이며,  n = 7 이므로 n log n을 계산해 보면 19.65 이다.  실제 연산 횟수가 18이었으므로 거의 비슷한 수치다.

 

반면 입력값이 [1, 2, 3, 4, 5, 6, 7] 이라면 48번의 연산을 수행한다. 이경우가 바로 최악의 경우 O(n²)에 가깝다. 실제로 n = 7 일때 n²의 값은 49로 거의 유사하다. 평균적으로는 입력값에 따라 24번 사이를 왔다 갔다 할 것이다.  즉  n = 7 일 때 최선, 평균, 최악의 경우에 연산 횟수는 각각 18, 24, 48 이 값은 n이 점점 커져도 비슷한 비율로 유지될 것이다. 

 

 

💡 tip) 퀵 정렬(Quick Sort)

퀵 정렬은 수열을 정렬하는 알고리즘 중 하나이다. 다른 알고리즘에 비해 비교 및 교환 횟수가 적은 것이 특징으로 대부분의 경우 빠른 속도록 정렬할 수 있다.

처음 작업 대상은 모든 숫자이다.  정렬의 기준이 되는 숫자를 하나 선택한다. 1)이 숫자를 피봇(pivot)이라고 부른다.피봇은 보통 하나의 숫자를 랜덤으로 선택한 것이다. 편의상 가장 오른쪽에 위치한 숫자하나를  피봇으로 선택하 표시를 한다. 계속해서 2)피봇 표시를 제외하고 가장 왼쪽의 숫자에는 왼쪽 마커 오른쪽의 숫자에는 오른쪽 마커를 한다. 퀵 정렬은 이 마커들을 사용해서 일련의 작업을 재귀적으로 반복하는 알고리즘이다.

3)왼쪽 마커를 오른쪽으로 이동한다. 그러다 왼쪽 마커는 피봇수 이상에 도달하면 멈추고, 4)오른쪽 마커는 피봇수 이하의 숫자에 도착하면 멈춘다. 5)좌우 마커가 모두 멈춘 시점에 마커의 숫자를 교체한다. 숫자를 교환하므로 수열의 왼쪽에 피봇보다 작은 수, 오른쪽에 피봇 이상인 수를 모을 수 있다.

6)두개 마커가 동일한 위치인 경우 해당 수를 피봇과 교환한다. 좌우 마커가 있는 수를 정렬 완료 상태로 둔다. 이것으로 첫 작업이 완료된다. 일련의 작업에 의해 수열은 피봇 왼쪽에는 '피봇보다 작은 수'로 피봇 오른쪽에는 '피봇보다 큰 수 '로 나눌수 있다. 둘로 나위어진 수열에 대해 일련의 작업을 재귀적으로 반복한다. 7)대상 수열의 수가 하나인 경우 정렬이 완료된다.

재귀작업을 반복하다가 왼쪽 마커가 오른쪽 끝에 도달하면 해당 숫자는 대상 범위에서 가장 큰 숫자이다. 다음은 오른쪽 마커의 이동 차례이지만 오른쪽 마커가 왼쪽 마커에게 추월당하면 더이상 움직이지 않고 움직임을 종료한다. 8)왼쪽 마커가 작업 대상의 오른쪽 끝에 도달한 경우, 해당 피봇 수를 정렬 완료 상태로 둔다.

 

그림 5-3 복잡한 함수의 n > n₀일 대 실행 상한과 하한

 

반면 빅오 표기는 그림 5-3과 같은 복잡한 함수 f(n)이 있을 경우, 이 함수의 실행 상한과 하한을 의미한다. 가장 빨리 실행될 때 (하한)가장 늦게 실행될 때(상한)를 뜻하며 이 중 가장 빨리 실행될 때를 빅 오(O), 가장 빨리 실행될 때를 빅 오메가(Ω), 평균적으로는 빅 세타(ϴ)로 지칭한다. 또한  빅오 표기법은 n이 작을 때, n₀ 이하로 값이 작은 경우는 무시하며, 빅오 표기법은 n이 매우 클 때의 전체적인 큰 그림에 집중한다.

 

다시 퀵정렬을 예로 들자면 '최선의 경우 O(n log n)이다.' 라는 말은 입력값이[1, 4, 3, 7, 8, 6, 5]로 최선일 때  연산의 상한이 n log n 이내 라는 얘기이다.  여기서  n log n을 계산한 결과는 19.65이므로, 실제 연산 횟수인 18인 더 작은 값이므로 19.65에 속한다. 

 

 

정리

•  퀵 정렬의 시간 복잡도는 최악의 경우 O(n²)이며, 최선의 경우 O(n log n)이다.
• 빅오 표기법은 주어진 (최선/최악/평균)경우의 수행 시간의 상한을 나타낸다.