2.1.1 빅오 표기법

코딩 테스트에서 효율성을 검사하는 데 사용하는 시간 복잡도는 빅오(Big-O) 표기법을 사용합니다. 빅오 표기법은 알고리즘이 겪을 수 있는 최악의 경우에 걸리는 시간과 입력 간의 상관관계를 표기합니다. 입력 크기가 N이고, 이에 비례하는 시간이 걸린다면 O(N)으로 표기합니다.

길이가 N인 배열에서 하나의 원소를 찾는 다음 코드를 살펴봅시다.

private int search(int[] array, int target) {
    for (int i = 0; i < array.length; i++) {
        if (array[i] == target) {
            return i;
        }
    }
    return -1;
}

이 코드는 평균적으로 배열 중간쯤에서 원소를 찾게 될 것입니다. 하지만 최악의 경우에는 모든 원소를 순회한 후 원소를 찾게 됩니다. 즉, 전체 배열을 순회하므로 O(N) 시간 복잡도를 갖게 됩니다.

코딩 테스트에서 효율성을 묻는 문제는 문제 제한 사항에 명시되어 있는 조건을 극한으로 맞추는 입력 데이터를 사용해서 코드를 평가합니다. 따라서 입력될 수 있는 최악의 상황을 상정하여 시간 복잡도를 계산할 수 있도록 빅오 표기법을 사용합니다.