[DSA] 빅오 표기법

개요

빅 오(Big O)는 알고리즘의 계산 복잡도를 설명하는 데 사용되는 표기법이다. 알고리즘의 계산 복잡도는 시간 복잡도와 공간 복잡도로 나눌 수 있다.

시간 복잡도: 입력의 크기에 따른 알고리즘 실행 시간
공간 복잡도: 입력의 크기에 따른 알고리즘 실행 중 사용하는 메모리 양

사람들은 공간 복잡도보다 시간 복잡도를 더 중요시하지만, 두 복잡도 모두 이해하고 있으면 좋다.

복잡도의 작동 방식

복잡도를 나타내는 함수는 프로그래머가 결정하는 매개변수에 따라 달라진다. 이 매개변수들은 입력 데이터의 변화에 따라 영향을 받는 모든 주요 변수들을 포함해야 한다. 일반적으로, $n$이라는 변수가 자주 쓰이며, 이는 입력된 배열이나 문자열의 길이를 의미한다.

면접 상황에서, 대규모 데이터 처리 시 연산에 더 많은 시간이 소요된다는 것은 사실하다. 하지만, 빅오 상황에서는 시간의 차이는 그리 크지 않아 크게 중요하지 않다. 정수 배열이 주어졌을 때, $n$, 즉 배열의 길이는 중요한 변수로 간주된다. 추가적으로 배열의 평균값 등 다른 상세 정보를 나타내는 변수를 빅오 표기법에 포함시킬 수도 있지만, 일반적으로 이렇게 하지는 않는다.

복잡도 함수는 대문자 $O$로 표현되며, 다음과 같은 예시들이 있다:

$O(n)$
$O(n^2)$
$O(2^n)$
$O(\log{}n)$
$O(n \cdot m)$

$m$이 무엇인지 의문을 가질 수 있다. 중요한 것은, 변수는 우리가 설정한다는 것이다. $m$은 단순히 예시에 불과하고, $m$는 어떤 임의의 변수가 될 수도 있다. 예를 들어, 두 개의 배열을 입력으로 하는 문제에서, $n$은 한 배열의 길이를, $m$은 다른 배열의 길이를 나타낼 수 있다.

규칙

빅오 표기법은 알고리즘의 성능 변화를 설명하는 데 사용된다. 이 때 변수가 무한으로 커질 때, 상수는 무시된다.

예시: $O(9999999n) = O(8n) = O(n) = O(\frac{n}{500})$ 가 된다.

중요한 것은 “입력의 크기가 증가함에 따라 알고리즘이 어떻게 반응하는가”이다.
예를 들어, 두 알고리즘이 있고, 하나는 $O(100n)$에, 다른 하나는 $O(5n)$에 의해 동작한다고 가정해보자. $n$이 두 배가 되면, 두 알고리즘의 실행 시간 또한 두 배가 될 것이다.
하지만 두 알고리즘의 실행 시간이 $n$의 크기에 따라 선형적으로 증가하기 때문에, 둘 다 $O(n)$으로 분류된다.

복잡도를 계산할 때 동일한 변수에 대한 여러 항이 더해지거나 빼질 때, 가장 큰 영향을 주는 항만 고려한다. 예를 들어, $O(2n + n^2 - 500)$ = $O(n^2)$에서는 $n^2$항이 가장 큰 영향을 주기 때문에 다른 항은 고려하지 않는다.

알고리즘의 성능을 분석하고 예측하는 능력은 굉장히 중요하다. 면접에서도 종종 이러한 종류의 문제를 통해 분석 능력을 검증한다.

“상수 시간”이나 “상수 공간” 복잡도는 $O(1)$로 나타낸다. 이는 입력의 크기와 무관하게 알고리즘의 성능이 일정하다는 것을 의미한다.
그렇지만, 시간 복잡도가 일정하다고 해서 항상 알고리즘이 빠르다는 의미는 아니다. 이는 복잡도가 입력의 크기와 관계없이 일정하다는 것을 나타낼 뿐이다. ($O(50000000) = O(1)$)

알고리즘 성능을 평가할 때, 고려하는 세 가지 주요 시나리오는 다음과 같다:

최적의 경우
평균적인 경우
최악의 경우

대다수 알고리즘에서는 이 세 가지 시나리오에 따른 성능이 크게 다르지 않을 수 있다. 하지만, 일부 알고리즘에서는 이들 각각의 성능이 상이할 수 있다. 복잡도를 딱 하나의 시나리오에 근거하여 표현해야 한다면, 최적의 상황을 기준으로 삼으면 안 된다. 일반적으로 최악의 경우를 기준으로 알고리즘의 복잡도를 분석하는 것이 가장 정확하다. 물론 이들 각각의 성능 차이를 이해하고 있는 편이 좋다.

시간 복잡도 분석

간단한 의사 코드 예제를 통해 시간 복잡도를 분석해보자.

// 길이가 n인 정수 배열 "arr"이 주어진다.

for (int num: arr) {
    print(num)
}

이 알고리즘의 시간 복잡도는 $O(n)$이다. 각 반복마다 $O(1)$의 비용이 드는 출력 작업을 $n%번 수행하므로 전체 시간 복잡도는 $O(1 \cdot n) = O(n)$이다.

// 길이가 n인 정수 배열 "arr"이 주어진다.

for (int num: arr) {
    for (int i = 0; i < 500,000; i++) {
        print(num)
    }
}

이 코드의 시간 복잡도도 $O(n)$이지만, 실제 실행 시간은 첫 번째 예제보다 훨씬 길다. 이유는 각 요소를 출력하는 횟수가 $500,000$번으로 매우 많기 때문이다. 그러나 이론적인 분석에서는 이 내부 반복 작업의 시간이 고정되어 있어 복잡도 계산에 있어서는 크게 영향을 미치지 않는다.

// 길이가 n인 정수 배열 "arr"이 주어진다.

for (int num: arr) {
    for (int num2: arr) {
        print(num * num2)
    }
}

이 알고리즘의 시간 복잡도는 $O(n^2)$이다. 처리해야 할 작업이 $n$에 대하여 제곱으로 증가한다. 따라서 전체 시간 복잡도는 $O(n \cdot n)=O(n^2)$이다.

// 길이가 n인 정수 배열 "arr"와 길이가 m인 "arr2"가 주어진다.

for (int num: arr) {
    print(num)
}

for (int num: arr) {
    print(num)
}

for (int num: arr2) {
    print(num)
}

이 알고리즘의 시간 복잡도는 $O(n + m)$이다. 알고리즘은 세 개의 순차적인 단계로 구성되어 있으며, 각 배열을 순회하면서 출력한다. 따라서 전체 작업량은 두 배열의 길이 합, 즉 $O(2n + m) = $O(n + m)$에 해당한다.

// 길이가 n인 정수 배열 "arr"이 주어진다.

for (int i = 0; i < arr.length; i++) {
    for (int j = i; j < arr.length; j++) {
        print(arr[i] + arr[j])
    }
}

이 알고리즘의 시간 복잡도는 $O(n^2)$이다. i번째 이후의 모든 요소와의 합을 계산한다. 반복문이 점진적($n-1$번, $n-2$번, $n-3$번…)으로 줄어들지만, 총 연산 횟수는 여전히 $n$에 대해 제곱에 비례한다.

즉, 전체 반복 횟수는 $1 + 2 + 3 + … + n$이며, 이 수열의 합은 $\frac{n \cdot (n+1)}{2} = \frac{n^2 + n}{2}$이다. 빅오 표기에서는 고차 항만을 고려하므로, 시간 복잡도는 $O(n^2)$이 된다.

로그 시간

로그는 지수의 역연산에 해당한다. 시간 복잡도 $O(\log{}n)$은 로그 시간이라고 불리며, 이는 매우 빠른 시간 복잡도에 속한다. 일반적으로 효율적인 정렬 알고리즘의 시간 복잡도로 $O(n \cdot \log{}n)$ 이 많이 사용된다.

로그의 밑은 흔히 2가 사용되지만, 빅오 표기법에서는 로그의 밑이 크게 중요하지 않다. 이는 모든 로그가 상수 배율로 변환될 수 있기 때문이다. $O(\log{}n)$은 알고리즘이 각 단계에서 문제의 크기를 일정 비율로 줄인다는 것을 의미한다. 이와 같은 방식으로 작동하는 대표적인 예시 알고리즘은 이진 탐색(Binary Search)이 있다. 이진 탐색은 검색 범위를 각 단계마다 반으로 줄여나가므로 $O(\log{}n)$의 시간 복잡도를 가진다.

공간 복잡도 분석

알고리즘이 변수나 데이터 구조를 초기화할 때는 메모리 공간이 필요하다. 이때 입력 데이터에 필요한 메모리는 제외하고, 추가적으로 할당되는 메모리만을 공간 복잡도의 계산에 포함한다. (물론 입력 데이터 자체를 수정하는 행위는 되도록 피해야 한다.) 일반적으로 코딩 테스트 환경에서는 출력 결과에 사용되는 메모리도 별도로 고려하지 않는다.

다음 예제들은 각 알고리즘의 공간 복잡도를 분석하기 위한 것으로, 필요한 메모리 할당을 강조하여 설명한다. 정해진 “정답”은 없으며, 상황에 따라 다를 수 있다.

// 길이가 n인 정수 배열 "arr"이 주어진다.

for (int num: arr) {
    print(num)
}

위 알고리즘의 공간 복잡도는 $O(1)$이다. 여기서 할당되는 유일한 메모리는 반복문의 각 단계에서 임시적으로 사용되는 정수 변수 num으로, 이는 입력 크기 $n$과 무관하게 일정한 공간만을 차지한다.

// 길이가 n인 정수 배열 "arr"이 주어진다.

Array doubledNums = int[]

for (int num: arr) {
    doubledNums.add(num * 2)
}

위 알고리즘의 공간 복잡도는 $O(n)$이다. doubledNums 배열은 입력 배열과 동일한 수의 원소를 가지므로, $n$에 비례하는 메모리가 필요하다.

// 길이가 n인 정수 배열 "arr"이 주어진다.

Array nums = int[]
int oneHundredth = n / 100

for (int i = 0; i < oneHundredth; i++) {
    nums.add(arr[i])
}

위 알고리즘의 공간 복잡도는 $O(n)$이다. 비록 nums 배열이 입력의 처음 1%에 해당하는 원소만 arr에 저장하지만, 공간 복잡도 분석에서는 최악의 경우를 기준으로 하기 때문에 $O(\frac{n}{100}) = O(n)$이라 할 수 있다.

// 길이가 n인 정수 배열 "arr"와 길이가 m인 "arr2"가 주어진다.

Array grid = int[n][m]

for (int i = 0; i < arr.length; i++) {
    for (int j = 0; j < arr2.length; j++) {
        grid[i][j] = arr[i] * arr2[j]
    }
}

위 알고리즘의 공간 복잡도는 $O(n \cdot m)$이다. grid에는 $n \cdot m$크기의 2차원 배열 grid에 할당되므로, 이에 따라 필요한 메모리 공간도 $n$과 $m$의 곱에 비례한다.

시간 복잡도와 공간 복잡도는 알고리즘의 효율성을 평가하는 중요한 기준이다. 처음에는 복잡해 보일 수 있으나, 지속적인 연습을 통해 이해도를 높이고 응용 능력을 키울 수 있다.

출처: Leetcode