빅오표기법(Big O notation)

프로그래밍 문제를 해결하는 데에는 여러가지 방법이 있다. 어떤 방법이 다른 방법보다 나은지(어떤 방법을 선택할지) 어떻게 알 수 있을까?

알고리즘이 어떤 문제를 해결하는 데 걸리는 시간을 시간복잡도(Time complexity)라고 하고 주로 빅오표기법(Big O notation)을 이용해 나타낸다. 입력값이 n개 일 때 걸리는 시간을 비교해 알고리즘의 효율성을 표현하기 위한 방식이다. 이 때 n의 값은 충분히 크다고 가정한다.

n의 값에 따른 알고리즘의 시간복잡도는 다음과 같다.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) < O(nⁿ)

이해를 돕기 위해 예시를 보자. 다음 코드는 크기가 n인 정수배열에서 0보다 작은 값이 있으면 true, 없으면 false를 반환한다. 시간복잡도를 계산해보자.

public boolean hasNegativeNumber(int array[]){
 
    if(array==null){
        return false;
    } 
 
    for(int i=0 ; i<array.length ; i++){
        if(array[i]<0){
            return true;
        }
    }
    return false;
}
 

배열을 순서대로 탐색하므로 만약 array[0]의 값이 음수라면 시작하자마자 결과가 나오겠지만(best case) 음수가 배열의 맨 마지막에 있다면array[n]까지 탐색해야하므로(worst case) n만큼의 시간이 걸린다. 하지만 아무리 최악의 경우라도 O(n)보다 시간이 더 걸리지는 않는다. 위의 코드의 시간복잡도는 O(n)이다.

두번째로는 정수배열과 목표값을 입력으로 받아 배열 요소의 값의 합이 목표값과 일치하는 인덱스를 찾아 반환하는 코드를 보자.

public int[] twoSum(int[] nums, int target) {
    for (int i = 0; i < nums.length; i++) {
        for (int j = i + 1; j < nums.length; j++) {
            if (nums[j] == target - nums[i]) {
                return new int[] { i, j };
            }
        }
    }
    throw new IllegalArgumentException("No two sum solution");
}

이중 for문을 사용하므로 최대 n(n-1)/2만큼의 시간이 걸린다. 우리는 n이 충분히 큰 수라고 가정하기 때문에 가장 큰 항에서 상수는 무시하고 따라서 이 경우 시간복잡도는 O(n²)이다.

Big O notation은 실행시간이 꼭 그만큼 걸린다기 보다는 실행시간의 최댓값은 이정도이기때문에 '아무리 최악의 케이스여도 이정도 속도까지는 보장한다'라고 이해하면 된다.