최선의 경우

최선의 경우는 같은 크기의 입력 가운데 알고리즘이 가장 일찍 끝나는 입력입니다. 목록에서 맨 앞에 놓인 값을 찾으면 한 번 보고 바로 끝납니다. 이 입력에서 드는 일을 재면 알고리즘의 바닥을 알 수 있습니다. 어떤 입력을 넣어도 이보다 적게 일하지는 않습니다.

상세

출근길에 신호등이 열 개 있다고 해 봅시다. 신호가 전부 초록불인 날에는 한 번도 서지 않고 회사에 닿습니다. 같은 길인데도 그날 신호가 어떻게 걸리느냐에 따라 걸리는 시간이 달라집니다. 신호가 모두 초록불인 날이 이 출근길의 최선의 경우입니다.

알고리즘이 하는 일의 양도 입력에 따라 달라집니다. 입력이 크면 대개 일이 늘어납니다. 그런데 크기가 같아도 값이 놓인 모양에 따라 일의 양이 달라집니다.

입력이 얼마나 큰지는 흔히 n 이라고 적습니다. 목록을 다루는 알고리즘이면 목록에 든 값의 개수가 n 입니다. 이 값을 입력 크기라고 부릅니다.

최선의 경우는 크기가 n 인 입력들 가운데 일이 가장 적게 드는 입력입니다. 그 입력에서 드는 일의 양이 최선의 경우 비용입니다. 영어로는 best case 라고 합니다.

최선의 경우 비용은 알고리즘의 바닥을 알려 줍니다. 크기가 n 인 입력이라면 어떤 입력을 넣어도 이보다 적게 일하고 끝나지는 않습니다.

비용을 입력의 경우마다 따로 재는 까닭이 있습니다. 경우를 밝히지 않으면 비용을 한 가지로 말할 수 없습니다. 목록에서 값을 찾는 데 비교가 몇 번 드느냐고 물으면 한 번이라는 답도, 목록 길이만큼이라는 답도 맞습니다.

그래서 비용을 말할 때는 세 경우를 나눠 씁니다. 일이 가장 적은 입력이 최선의 경우입니다. 일이 가장 많은 입력이 최악의 경우입니다. 입력이 고르게 들어온다고 보고 평균을 낸 것이 평균의 경우입니다.

순차 탐색에서 세어 보기

순차 탐색은 목록의 값을 앞에서부터 하나씩 보며 찾는 값과 같은지 비교합니다. 같은 값을 만나면 그 위치를 돌려주고 멈춥니다. 끝까지 없으면 -1 을 돌려줍니다. 아래는 순차 탐색을 자바로 적은 함수입니다.

int find(int[] a, int x) {
    for (int i = 0; i < a.length; i++) {
        if (a[i] == x) return i;
    }
    return -1;
}

이 함수에 값 넷이 든 배열을 넣어 봅니다. 줄마다 오른쪽 주석은 돌려받는 값과 비교 횟수입니다.

int[] a = {7, 3, 9, 5};
find(a, 7);   // 0 · 비교 1번
find(a, 5);   // 3 · 비교 4번
find(a, 8);   // -1 · 비교 4번

7 은 맨 앞에 있어서 한 번 비교하고 끝납니다. 이 입력이 최선의 경우입니다. 5 는 맨 끝에 있습니다. 8 은 아예 없습니다. 둘 다 네 값을 모두 봐야 해서 최악의 경우입니다.

값이 여덟 개인 목록으로 늘려 봅니다. 찾는 값이 k 번째에 있으면 비교를 k 번 합니다. 아래 막대는 찾는 값의 위치마다 든 비교 횟수입니다.

xychart-beta
    title "찾는 값의 위치와 비교 횟수"
    x-axis "찾는 값의 위치" [1, 2, 3, 4, 5, 6, 7, 8]
    y-axis "비교 횟수" 0 --> 8
    bar [1, 2, 3, 4, 5, 6, 7, 8]

가장 낮은 첫 막대가 최선의 경우 비용입니다. 가장 높은 마지막 막대가 최악의 경우 비용입니다. 찾는 값이 여덟 위치 어디에나 고르게 놓인다고 보고 여덟 막대를 평균 내면 4.5 번입니다. 이것이 평균의 경우 비용입니다.

입력이 커질 때 일이 어떤 꼴로 늘어나는지 적는 방법이 빅오 표기법입니다. 일이 n 과 상관없이 일정하면 O(1) 로 적습니다. 일이 n 에 비례해 늘면 O(n) 으로 적습니다.

순차 탐색의 최선의 경우 비용은 목록이 아무리 길어도 비교 한 번이라 O(1) 입니다. 최악의 경우 비용은 목록 길이만큼 비교하므로 O(n) 입니다.

입력 크기는 먼저 정해 둔다

최선의 경우라는 말을 처음 들으면 빈 목록이나 값이 하나뿐인 목록을 떠올리기 쉽습니다. 이런 입력은 최선의 경우가 아닙니다. 최선의 경우는 크기를 n 으로 정해 둔 뒤에 그 크기의 입력들 안에서 고릅니다.

입력이 작으면 어떤 알고리즘이든 일이 적습니다. 크기를 줄여서 얻은 짧은 시간은 알고리즘에 대해 아무것도 알려 주지 않습니다. 알고 싶은 것은 크기가 같을 때 입력의 모양이 비용을 얼마나 바꾸느냐입니다.

그래서 최선의 경우 비용은 n 에 대한 식으로 나옵니다. 순차 탐색은 n 이 얼마든 1 입니다. n 이 커지면 같이 커지는 알고리즘도 있습니다. 아래 정렬 소절에서 그런 예를 봅니다.

최선의 경우와 빅오메가

최선의 경우를 빅오메가 표기법과 같은 것으로 외우는 일이 흔합니다. 둘은 서로 다른 질문에 답합니다. 순차 탐색을 예로 그 차이를 가릅니다.

앞에서 순차 탐색의 비용을 O(1)·O(n) 으로 적었습니다. 이 빅오는 엄밀히는 「많아도 이만큼」이라는 위쪽 선입니다. 이 위쪽 선을 상한이라고 부릅니다. 최악의 경우 비용 O(n) 은 많아도 n 에 비례하는 만큼 비교한다는 뜻입니다.

빅오메가는 반대쪽 선을 적습니다. 「적어도 이만큼은 든다」는 아래쪽 선입니다. 이 아래쪽 선을 하한이라고 부릅니다. 기호는 Ω 입니다. 빅오와 빅오메가는 위아래로 짝을 이룹니다.

상한과 하한이 같은 꼴이면 빅세타 표기법으로 적습니다. 기호는 Θ 입니다. 순차 탐색의 최선의 경우 비용은 늘 1 이라 Θ(1) 입니다.

최선의 경우는 어느 입력을 두고 잴지를 정합니다. 빅오와 빅오메가는 그렇게 잰 비용 식의 위와 아래 중 어느 쪽을 말할지를 정합니다. 두 축은 따로 움직입니다. 아래 표가 두 축을 나란히 놓은 것입니다.

표의 두 줄에서 하나씩 골라 짝지을 수 있습니다. 최선의 경우에도 빅오를 쓸 수 있습니다. 앞에서 적은 「순차 탐색의 최선의 경우 비용은 O(1)」이 바로 그 예입니다. 거꾸로 최악의 경우에도 빅오메가를 쓸 수 있습니다. 순차 탐색의 최악의 경우 비용은 적어도 n 에 비례하므로 Ω(n) 입니다.

그런데도 둘을 한데 묶어 외우게 되는 까닭은 경우를 밝히지 않은 빅오메가에 있습니다. 「이 알고리즘은 적어도 이만큼 든다」고만 말하면 그 말은 모든 입력에서 맞아야 합니다.

순차 탐색으로 보면 이렇습니다. 「순차 탐색은 적어도 n 번 비교한다」는 틀린 말입니다. 찾는 값이 맨 앞에 있으면 한 번에 끝나기 때문입니다. 모든 입력에서 맞는 하한은 비교 한 번뿐입니다. 이 값은 최선의 경우 비용과 같습니다.

경우를 밝히지 않은 빅오메가가 최선의 경우 비용의 하한으로 모이는 까닭이 이것입니다. 그래도 둘이 같은 개념은 아닙니다. 최선의 경우는 입력을 고릅니다. 빅오메가는 선의 방향을 고릅니다.

정렬 알고리즘마다 갈리는 최선의 경우

정렬 알고리즘 셋을 놓고 최선의 경우가 알고리즘마다 얼마나 다른지 봅니다. 셋 다 목록을 작은 값부터 늘어놓는 같은 일을 합니다. 그런데 최선의 경우가 오는 입력도, 그때의 비용도 다릅니다.

삽입 정렬은 값을 하나씩 꺼내 앞쪽에 정렬해 둔 부분의 알맞은 곳에 끼웁니다. 끼울 곳을 찾으려고 앞의 값들과 뒤에서부터 비교합니다. 이미 정렬된 목록이 들어오면 값마다 바로 앞 하나와 비교하고 끝납니다. 비교가 n − 1 번이라 최선의 경우 비용은 O(n) 입니다.

거꾸로 정렬된 목록은 삽입 정렬의 최악의 경우입니다. 값마다 앞쪽을 끝까지 거슬러 가며 비교해야 합니다. 비교가 n 의 제곱에 비례해 늘어서 O(n²) 입니다.

선택 정렬은 남은 값 가운데 가장 작은 값을 찾아 앞으로 보냅니다. 가장 작은 값을 찾으려면 남은 값을 전부 봐야 합니다. 목록이 이미 정렬돼 있어도 이 일을 건너뛸 수 없습니다. 최선의 경우 비용도 최악의 경우 비용과 같은 O(n²) 입니다.

퀵 정렬은 값 하나를 기준으로 골라 그보다 작은 값과 큰 값으로 목록을 나눕니다. 이 기준값을 피벗이라고 부릅니다. 나눈 두 쪽은 같은 방법으로 다시 정렬합니다.

피벗이 매번 목록을 절반으로 나누면 퀵 정렬의 최선의 경우입니다. n 을 절반씩 나눠 1 이 될 때까지 걸리는 횟수를 log n 이라고 적습니다. 아래 그림처럼 나누기는 층으로 쌓입니다. 층마다 조각 수는 두 배로 늘지만 조각을 다 합치면 늘 값 n 개입니다.

flowchart TD
    subgraph L1["1층 · 합계 n 개"]
        A["n 개"]
    end
    subgraph L2["2층 · 합계 n 개"]
        B1["n/2 개"]
        B2["n/2 개"]
    end
    subgraph L3["3층 · 합계 n 개"]
        C1["n/4 개"]
        C2["n/4 개"]
        C3["n/4 개"]
        C4["n/4 개"]
    end
    D["… 조각이 1 개가 될 때까지 · 모두 log n 층"]
    A --> B1
    A --> B2
    B1 --> C1
    B1 --> C2
    B2 --> C3
    B2 --> C4
    L3 --> D

층이 log n 개입니다. 층마다 값 n 개를 한 번씩 보므로 최선의 경우 비용은 O(n log n) 입니다.

피벗이 매번 가장 작은 값이면 한쪽이 늘 빕니다. 피벗 하나를 뺀 나머지는 전부 다른 쪽으로 갑니다. 조각이 한 층에 하나씩만 줄어듭니다. 이것이 퀵 정렬의 최악의 경우입니다.

flowchart TD
    A["n 개"] --> A0["빈 쪽"]
    A --> B["n − 1 개"]
    B --> B0["빈 쪽"]
    B --> C["n − 2 개"]
    C --> D["… 한 층에 하나씩 줄어 모두 n 층쯤"]

층이 log n 개가 아니라 n 개쯤 쌓입니다. 층마다 남은 값을 모두 보므로 O(n²) 이 됩니다.

세 알고리즘을 표로 모으면 이렇습니다.

선택 정렬 줄처럼 두 비용이 같으면 입력의 모양이 비용을 못 바꾼다는 뜻입니다. 삽입 정렬 줄처럼 둘이 크게 벌어지면 입력의 모양을 알 때 걸리는 시간을 훨씬 좁게 가늠할 수 있습니다.

최선의 경우가 말해 주지 않는 것

최선의 경우는 알고리즘의 바닥을 알려 주지만 성능을 약속하지는 않습니다. 이 소절은 그 까닭 둘과, 그래도 최선의 경우 비용이 드러나는 때를 봅니다.

첫째, 최선의 경우는 드물게 옵니다. 순차 탐색에서 찾는 값이 늘 맨 앞에 있으리라고 기대할 수는 없습니다. 그래서 응답 시간처럼 지켜야 할 값을 약속할 때는 최악의 경우나 평균의 경우를 씁니다.

둘째, 최선의 경우는 값싸게 바꿀 수 있습니다. 어떤 정렬 알고리즘이든 시작하기 전에 목록이 이미 정렬돼 있는지 한 번 훑게 만들 수 있습니다. 정렬돼 있으면 바로 끝냅니다. 이 검사 하나로 최선의 경우 비용이 O(n) 이 됩니다.

최악의 경우 비용은 이렇게 손쉽게 줄지 않습니다. 검사를 덧붙여도 정렬이 안 된 목록에서는 원래 하던 일을 다 해야 합니다. 그래서 최선의 경우 비용만 보고 알고리즘끼리 견주면 거의 아무것도 가려지지 않습니다.

그래도 입력이 최선의 경우에 가까우면 이 비용이 그대로 드러납니다. 정렬해 둔 목록 끝에 값 몇 개를 덧붙이고 다시 정렬하는 일을 떠올려 봅시다. 삽입 정렬은 이런 거의 정렬된 목록에서 값마다 몇 번만 비교하고 끝납니다.

이런 입력이 자주 오면 일찍 끝내는 검사를 알고리즘 안에 넣기도 합니다. 버블 정렬은 목록을 여러 번 훑습니다. 훑을 때마다 이웃한 두 값을 비교해 순서가 틀리면 맞바꿉니다. 한 번 훑는 동안 맞바꾼 것이 없으면 이미 정렬된 것이니 거기서 멈추게 할 수 있습니다. 그러면 정렬된 목록은 한 번 훑고 끝나 O(n) 입니다.

관련 항목

최선의 경우와 함께 비용을 나누는 분석 기준

최악의 경우 · 평균의 경우 · 분할 상환 비용 · 평균 · 확률적 분석

최선의 경우 비용을 적는 표기와 잣대

빅오 표기법 · 빅오메가 표기법 · 빅세타 표기법 · 점근 분석 · 시간 복잡도 · 공간 복잡도 · 입력 크기 · 복잡도

최선의 경우를 따져 보는 알고리즘

알고리즘 · 순차 탐색 · 이진 탐색 · 정렬 알고리즘 · 삽입 정렬 · 선택 정렬 · 버블 정렬 · 퀵 정렬 · 병합 정렬 · 피벗

최선의 경우와 헷갈리는 이웃

하한 · 상한 · 최적 알고리즘 · 비교 정렬 하한

거의 정렬된 입력에서 일을 줄이는 기법

조기 종료 · 적응형 정렬 · 팀 정렬 · 역순쌍