최악의 경우

최악의 경우는 코드에 일을 가장 많이 시키는 입력에서 드는 비용을 알려 줍니다. 이 비용은 어떤 입력이 와도 넘지 않는 선이 됩니다. 그래서 알고리즘의 성능을 말할 때 가장 흔히 기준으로 삼습니다.

상세

면접이 있는 날 집을 나서는 때를 떠올려 봅시다. 출근길이 보통 30분 걸려도 그날은 가장 막혔던 날의 50분을 기준으로 잡습니다. 그래야 길이 어떻든 늦지 않는다고 장담할 수 있습니다.

최악의 경우는 이 셈을 코드에 옮긴 것입니다. 크기가 같은 입력 가운데 코드에 일을 가장 많이 시키는 입력을 고릅니다. 그 입력에서 드는 비용이 그 크기의 최악의 경우입니다. 영어로는 worst case 라고 합니다.

입력 크기는 입력이 얼마나 큰지를 나타내는 수입니다. 목록이라면 든 원소의 수입니다. 흔히 n 으로 적습니다. 크기가 같아도 내용이 다른 입력은 여럿 있습니다. 원소 네 개짜리 목록만 해도 원소를 어떤 순서로 담느냐에 따라 입력이 달라집니다.

비용은 연산을 몇 번 하느냐로 셉니다. 초 단위 시간은 컴퓨터마다 달라서 쓰지 않습니다. 탐색과 정렬에서는 값끼리 견주는 비교 횟수를 흔히 셉니다.

아래에서는 먼저 두 알고리즘에서 최악의 입력을 찾아 비교 횟수를 셉니다. 그다음 이 경우가 성능을 말하는 기본 기준이 된 까닭을 봅니다. 이어서 이름이 비슷한 다른 기준들과 무엇이 다른지 가릅니다. 그 뒤에 최악의 입력을 일부러 만드는 공격과 이 기준이 놓치는 것을 봅니다. 끝으로 최악을 초 단위로 따지는 실시간 시스템을 봅니다.

순차 탐색의 최악의 입력

순차 탐색은 목록을 앞에서부터 하나씩 견주며 값을 찾습니다. 찾으면 거기서 멈춥니다. 그래서 찾는 값이 어디 있느냐에 따라 비교 횟수가 달라집니다.

아래 코드는 원소 네 개짜리 목록에서 값 네 개(7·9·5·8)를 차례로 찾습니다. 오른쪽 주석은 돌려주는 값과 비교 횟수입니다.

def find(xs, target):
    for i, x in enumerate(xs):
        if x == target:
            return i
    return -1

xs = [7, 3, 9, 5]
find(xs, 7)  # 0 · 비교 1번
find(xs, 9)  # 2 · 비교 3번
find(xs, 5)  # 3 · 비교 4번
find(xs, 8)  # -1 · 비교 4번

맨 앞의 7 은 한 번 견주고 끝납니다. 맨 끝의 5 는 네 번을 다 견줍니다. 목록에 없는 8 도 끝까지 가 봐야 없다는 것을 압니다.

순차 탐색의 최악의 입력은 찾는 값이 맨 끝에 있거나 아예 없는 목록입니다. 원소가 n 개면 비교는 n 번입니다. 이 n 번이 크기 n 에서의 최악의 경우입니다.

삽입 정렬의 최악의 입력

삽입 정렬은 원소를 앞에서부터 하나씩 꺼냅니다. 꺼낸 원소를 앞쪽에 이미 정렬해 둔 부분의 알맞은 곳에 끼웁니다. 끼울 곳을 찾으려고 바로 앞 원소부터 거꾸로 견주어 갑니다.

이미 정렬된 목록이 들어오면 원소마다 바로 앞 원소와 한 번만 견줍니다. 앞 원소가 더 작으니 움직일 필요가 없습니다. 원소가 n 개면 비교는 n − 1 번입니다.

거꾸로 정렬된 목록이 들어오면 꺼낸 원소가 매번 맨 앞까지 가야 합니다. 두 번째 원소는 한 번, 세 번째는 두 번, 마지막 원소는 n − 1 번 견줍니다. 모두 더하면 n(n − 1)/2 번입니다. 이것이 삽입 정렬의 최악의 경우입니다.

아래 그림은 거꾸로 정렬된 [4, 3, 2, 1] 을 넣었을 때입니다. 한 줄 내려갈 때마다 정렬해 둔 부분이 한 칸씩 자랍니다. 꺼낸 원소는 매번 그 부분의 맨 앞까지 갑니다.

flowchart TD
    S0["처음 · 4 3 2 1"]
    S1["정렬해 둔 부분 3 4 · 남은 2 1"]
    S2["정렬해 둔 부분 2 3 4 · 남은 1"]
    S3["정렬해 둔 부분 1 2 3 4"]
    S0 -->|"3 을 꺼내 맨 앞까지 · 비교 1번"| S1
    S1 -->|"2 를 꺼내 맨 앞까지 · 비교 2번"| S2
    S2 -->|"1 을 꺼내 맨 앞까지 · 비교 3번"| S3

비교는 1 + 2 + 3 = 6 번입니다. 원소가 넷일 때의 n(n − 1)/2 와 같은 값입니다.

크기가 같아도 두 입력의 차이는 n 이 커질수록 벌어집니다. 원소가 다섯이면 4 번과 10 번입니다. 원소가 천 개면 999 번과 499,500 번으로 오백 배가 납니다.

아래 그림은 n 을 2 부터 8 까지 늘리며 두 입력의 비교 횟수를 그린 것입니다. 위쪽 선이 거꾸로 정렬된 입력입니다. 아래쪽 선은 이미 정렬된 입력입니다. 아래쪽은 곧게 오르고 위쪽은 갈수록 가파르게 휩니다.

xychart-beta
    title "삽입 정렬의 비교 횟수"
    x-axis "원소 수 n" [2, 3, 4, 5, 6, 7, 8]
    y-axis "비교 횟수" 0 --> 30
    line [1, 3, 6, 10, 15, 21, 28]
    line [1, 2, 3, 4, 5, 6, 7]

크기만으로는 비용이 안 정해진다는 뜻입니다. 그래서 비용을 말할 때는 어느 입력을 두고 쟀는지를 함께 밝힙니다.

최악의 경우가 기본 기준인 까닭

첫째 까닭은 보장입니다. 최악의 경우는 크기 n 의 어떤 입력이 와도 넘지 않는 선입니다. 이렇게 넘지 않는 선을 상한이라고 부릅니다. 일이 적은 입력으로 잰 비용은 이런 약속을 못 합니다.

둘째 까닭은 가정이 필요 없다는 점입니다. 최악의 경우는 입력이 어떻게 들어올지 짐작하지 않고 구합니다. 평균을 내려면 어떤 입력이 얼마나 자주 오는지를 먼저 가정해야 합니다. 그 가정이 실제와 어긋나면 평균도 어긋납니다.

셋째 까닭은 최악의 입력이 생각보다 자주 온다는 점입니다. 순차 탐색으로 목록에 없는 값을 찾는 일은 흔합니다. 이런 조회는 매번 최악의 경우를 치릅니다.

빅오 표기법은 입력이 커질 때 비용이 늘어나는 꼴을 적는 표기입니다. 순차 탐색의 최악은 O(n) 으로 적습니다. 입력이 두 배가 되면 일도 두 배가 되는 꼴입니다. 삽입 정렬의 최악은 O(n²) 입니다. 입력이 두 배가 되면 일은 네 배가 됩니다.

어느 경우인지 밝히지 않고 O(n) 이라고만 쓰면 대개 최악의 경우를 두고 하는 말입니다. 앞의 세 까닭 때문에 성능을 말하는 기본값이 최악의 경우로 굳었습니다.

최선의 경우와 평균의 경우

한 알고리즘의 비용은 흔히 세 경우로 나눠 말합니다. 최악의 경우 말고 나머지 둘은 무엇을 두고 재는지가 다릅니다.

최선의 경우는 일을 가장 적게 시키는 입력의 비용입니다. 순차 탐색이라면 찾는 값이 맨 앞에 있을 때의 한 번입니다. 이런 입력은 고를 수 없으니 성능을 약속하는 데는 잘 안 씁니다.

평균의 경우는 입력이 어떤 비율로 들어올지 가정하고 그 비용을 평균 낸 값입니다. 찾는 값이 목록 어디에나 같은 확률로 있다고 보면 순차 탐색은 절반쯤인 n/2 번을 견줍니다. 원소가 무작위 순서로 섞여 있다고 보면 삽입 정렬은 대략 최악의 절반을 견줍니다.

아래 표는 세 경우를 두 알고리즘에 나란히 놓은 것입니다.

두 알고리즘 모두 평균의 경우가 최악의 경우와 같은 꼴로 늘어납니다. n/2 는 n 과, n²/4 는 n² 과 같은 꼴입니다. 이 둘은 최악만 알아도 평균을 짐작할 수 있습니다. 뒤에서 볼 퀵 정렬과 해시테이블은 그렇지 않습니다.

경우와 표기의 차이

최악의 경우를 빅오와 같은 말로 여기는 일이 흔합니다. 둘은 다른 질문에 답합니다. 최악의 경우는 어느 입력을 두고 잴지를 정합니다. 빅오는 그렇게 잰 비용이 넘지 않는 선의 꼴을 적습니다.

그래서 최선의 경우에도 빅오를 붙입니다. 순차 탐색의 최선은 입력 크기와 상관없이 한 번입니다. 이것은 O(1) 로 적습니다.

선은 위에만 긋는 것이 아닙니다. 앞에서 본 상한은 비용을 위에서 덮는 선입니다. 비용이 적어도 이만큼은 든다고 아래에서 받치는 선도 있습니다. 이 선을 하한이라고 부릅니다.

하한이 있으면 더 빨라질 수 없다는 말을 할 수 있습니다. 삽입 정렬의 최악인 n(n − 1)/2 번은 위에서도 아래에서도 n² 꼴의 선에 붙습니다. 그러니 거꾸로 정렬된 입력에서는 n² 꼴보다 빨리 끝날 수 없습니다. 두 선을 긋고 가르는 방법은 점근 분석이 다룹니다.

분할 상환 비용과 다른 점

최악의 경우는 넣기나 찾기 같은 연산을 한 번 부를 때의 비용을 잽니다. 그 한 번 안에서 비교나 옮기기를 몇 번 하는지 세는 것입니다. 분할 상환 비용은 그 연산을 여러 번 이어서 부를 때 한 번에 돌아가는 몫을 잽니다. 둘 다 입력에 대한 가정 없이 구하는 보장입니다. 재는 단위가 한 번이냐 여러 번의 합이냐가 다릅니다.

동적 배열이 이 차이를 보여 줍니다. 동적 배열은 칸이 다 차면 더 큰 칸을 잡고 값을 전부 새 칸으로 옮기는 배열입니다. 값 넣기 한 번의 최악의 경우는 들어 있던 값 n 개를 다 옮기는 O(n) 입니다.

칸을 두 배씩 늘리면 옮기는 일은 드물게만 일어납니다. 아래 그림은 칸 하나에서 시작해 값을 여덟 개 넣는 동안입니다. 칸이 차면 칸 수가 두 배가 됩니다. 그때 들어 있던 값을 전부 새 칸으로 옮깁니다.

flowchart TD
    C1["칸 1 · 값 1개"]
    C2["칸 2 · 값 1개를 옮김"]
    C4["칸 4 · 값 2개를 옮김"]
    C8["칸 8 · 값 4개를 옮김"]
    C1 -->|"두 번째 넣기에서 칸이 참"| C2
    C2 -->|"세 번째 넣기에서 칸이 참"| C4
    C4 -->|"다섯 번째 넣기에서 칸이 참"| C8

여덟 번 넣는 동안 옮긴 값은 1 + 2 + 4 = 7 개입니다. 옮긴 값을 모두 더하면 늘 지금 칸 수보다 하나 적습니다. 칸 수는 넣은 값의 두 배를 넘지 않으니 넣기를 n 번 이어 하면 옮기기도 2n 번을 넘지 않습니다.

2n 번 안쪽의 옮기기를 넣기 n 번에 고르게 나누면 한 번에 돌아가는 몫은 옮기기 2 번 안쪽입니다. 그래서 넣기 한 번의 분할 상환 비용은 O(1) 입니다. 한 번만 보면 O(n) 입니다. 여러 번에 나눠 보면 O(1) 입니다.

평균과 최악이 크게 갈리는 알고리즘

평균의 경우와 최악의 경우가 다른 꼴로 늘어나는 알고리즘도 많습니다. 이런 알고리즘은 평소에 금방 끝나다가 특정 입력에서만 오래 걸립니다. 퀵 정렬과 해시테이블을 봅니다.

퀵 정렬은 기준이 되는 값 하나를 골라 그보다 작은 쪽과 큰 쪽으로 목록을 나눕니다. 나뉜 두 쪽에서 같은 일을 되풀이합니다. 이 기준값을 피벗이라고 부릅니다.

나누기를 몇 번 되풀이하는지부터 셉니다. 목록을 절반씩 나눠 조각이 원소 하나가 될 때까지 걸리는 횟수를 log n 이라고 적습니다. 원소가 8 개면 4, 2, 1 로 세 번 나누니 log 8 은 3 입니다. 원소가 천 개면 log n 은 10 쯤입니다.

피벗이 매번 가운데쯤 값이면 목록이 절반씩 줄어듭니다. 한 번 나눈 결과를 한 층으로 세면 층은 log n 개 생깁니다. 층마다 모든 조각을 합쳐 원소 n 개쯤을 피벗과 견줍니다. 비용은 n 에 log n 을 곱한 O(n log n) 입니다.

평균의 경우도 이 꼴입니다. 피벗이 한가운데가 아니어도 한쪽으로 크게 쏠리지만 않으면 층 수는 log n 꼴을 벗어나지 않습니다.

피벗으로 늘 맨 앞 원소를 고르는 퀵 정렬에 이미 정렬된 목록을 넣으면 사정이 바뀝니다. 맨 앞 원소가 늘 가장 작은 값입니다. 작은 쪽은 비고 나머지는 전부 큰 쪽에 남습니다. 나눌 때마다 원소가 하나씩만 줄어서 층이 n − 1 개 생깁니다.

아래 그림은 원소 8 개로 두 경우의 층을 그린 것입니다. 위는 피벗이 가운데쯤일 때입니다. 아래는 맨 앞 피벗에 정렬된 목록을 넣었을 때입니다.

flowchart TD
    subgraph G1["피벗이 가운데쯤 · 층 셋"]
        direction TD
        A0["8개"] --> A1["4개"]
        A0 --> A2["4개"]
        A1 --> B1["2개"]
        A1 --> B2["2개"]
        A2 --> B3["2개"]
        A2 --> B4["2개"]
        B1 & B2 & B3 & B4 --> C0["1개짜리 여덟"]
    end
    subgraph G2["맨 앞 피벗 · 정렬된 목록 · 층 일곱"]
        direction TD
        P8["8개"] --> E8["작은 쪽 0개"]
        P8 --> P7["큰 쪽 7개"]
        P7 --> E7["작은 쪽 0개"]
        P7 --> P6["큰 쪽 6개"]
        P6 --> PR["나머지 층 넷"]
        PR --> P1["큰 쪽 1개"]
    end
    C0 ~~~ P8

위는 층 셋에서 끝납니다. 층마다 원소 8 개쯤을 견줍니다. 아래는 층이 일곱까지 길어집니다. 층마다 견주는 수도 하나씩만 줄어듭니다.

아래쪽에서 층마다 견주는 수는 n − 1, n − 2, … , 1 입니다. 모두 더하면 n(n − 1)/2 번으로 삽입 정렬의 최악과 같습니다. 퀵 정렬의 최악의 경우는 O(n²) 입니다.

아래 그래프는 n 을 2 부터 8 까지 늘리며 n log n 과 n² 을 그린 것입니다. 위쪽 선이 n² 이고 아래쪽 선이 n log n 입니다. n 이 커질수록 두 선이 벌어지는 만큼 퀵 정렬의 평균과 최악이 벌어집니다.

xychart-beta
    title "n log n 과 n² 이 늘어나는 꼴"
    x-axis "원소 수 n" [2, 3, 4, 5, 6, 7, 8]
    y-axis "값" 0 --> 70
    line [4, 9, 16, 25, 36, 49, 64]
    line [2, 4.8, 8, 11.6, 15.5, 19.7, 24]

해시테이블은 키마다 들어갈 칸을 계산해 값을 넣습니다. 찾을 때도 같은 계산으로 칸을 바로 찾아갑니다. 키가 칸에 고르게 흩어지면 찾기는 평균 O(1) 입니다.

서로 다른 키가 같은 칸에 떨어지는 일을 해시 충돌이라고 합니다. 모든 키가 한 칸에 몰리면 그 칸의 키를 하나씩 견줘야 합니다. 찾기의 최악의 경우는 O(n) 입니다.

아래 그림은 칸 넷에 키 넷을 넣은 두 모양입니다. 위는 키가 칸에 고르게 흩어진 모양입니다. 아래는 키가 칸 1 에 몰린 모양입니다.

flowchart TD
    subgraph H1["키가 고르게 흩어짐"]
        direction TD
        U0["칸 0"] --> UA["키 A"]
        U1["칸 1"] --> UB["키 B"]
        U2["칸 2"] --> UC["키 C"]
        U3["칸 3"] --> UD["키 D"]
    end
    subgraph H2["키가 한 칸에 몰림"]
        direction TD
        V0["칸 0 · 비었음"]
        V1["칸 1"] --> VA["키 A"] --> VB["키 B"] --> VC["키 C"] --> VD["키 D"]
        V2["칸 2 · 비었음"]
        V3["칸 3 · 비었음"]
    end
    UA ~~~ V1

위에서는 어느 키든 칸을 찾아가 한 번 견주면 끝납니다. 아래에서 키 D 를 찾으려면 칸 1 에 매달린 키를 앞에서부터 네 번 견줘야 합니다.

최악의 입력을 노리는 공격

최악의 입력이 드물다는 믿음은 입력을 남이 고를 때 깨집니다. 서버는 요청에 담긴 키와 값을 받아 자료구조에 넣습니다. 요청을 보내는 쪽이 입력을 고를 수 있다는 뜻입니다.

공격자가 한 칸에 몰리는 키만 골라 보내면 해시테이블의 조회가 매번 최악의 경우가 됩니다. 요청 몇 개만으로 서버의 계산 시간을 오래 붙잡을 수 있습니다. 이런 공격을 해시 플러딩이라고 부릅니다. 서비스를 못 쓰게 만드는 서비스 거부 공격의 한 갈래입니다.

막는 방법은 공격자가 최악의 입력을 미리 알 수 없게 하는 것입니다. 해시테이블은 키의 칸을 계산할 때 밖에서 모르는 값을 섞습니다. 퀵 정렬은 피벗을 무작위로 골라 어떤 입력도 늘 최악이 되지는 않게 합니다. 이렇게 무작위를 섞는 알고리즘을 무작위 알고리즘이라고 부릅니다.

최악의 경우만 볼 때 놓치는 것

최악의 입력이 드물면 이 기준은 실제보다 비싸다고 말합니다. 퀵 정렬은 최악이 O(n²) 이라 최악도 O(n log n) 인 병합 정렬보다 비싸 보입니다. 그래도 피벗을 잘 고르면 최악이 거의 안 나옵니다. 그래서 평균이 짧은 퀵 정렬이 널리 쓰입니다.

최악의 경우는 비용의 꼴을 말할 뿐 그 입력이 얼마나 자주 오는지는 말하지 않습니다. 그래서 알고리즘을 고를 때는 최악과 평균을 함께 봅니다. 한 번의 지연도 허용되지 않는 시스템에서는 최악을 먼저 봅니다.

실시간 시스템의 최악 실행 시간

실시간 시스템은 정해진 시간 안에 반드시 답해야 하는 시스템입니다. 자동차의 브레이크 제어처럼 한 번만 늦어도 탈이 나는 곳이 그렇습니다. 이런 곳에서는 평균이 짧다는 것만으로 마감을 지킨다고 말할 수 없습니다.

그래서 실시간 시스템은 작업마다 최악 실행 시간을 구합니다. 줄여서 WCET(Worst-Case Execution Time)라고 부릅니다. 연산 횟수의 꼴을 보는 알고리즘 분석과 달리 특정 하드웨어에서 가장 오래 걸릴 때의 시간을 구합니다. 같은 생각을 초 단위로 옮긴 것입니다.

관련 항목

최악의 경우와 나란히 쓰는 분석 기준

최선의 경우 · 평균의 경우 · 분할 상환 비용 · 분할 상환 분석 · 평균

최악의 경우 비용을 적는 복잡도 잣대

시간 복잡도 · 공간 복잡도 · 빅오 표기법 · 빅오메가 표기법 · 빅세타 표기법 · 점근 분석 · 상한 · 하한 · 입력 크기 · 복잡도 · 알고리즘

평균과 최악의 경우가 크게 갈리는 알고리즘과 자료구조

순차 탐색 · 삽입 정렬 · 퀵 정렬 · 해시테이블 · 이진 탐색 트리 · 동적 배열 · 해시 충돌

최악의 경우를 비껴가는 설계

병합 정렬 · 힙 정렬 · 인트로 정렬 · 균형 이진 탐색 트리 · 무작위 알고리즘 · 피벗

최악의 입력을 노리는 공격

해시 플러딩 · ReDoS · 알고리즘 복잡도 공격 · 서비스 거부 공격

최악의 경우를 시간 단위로 따지는 시스템과 지표

실시간 시스템 · 실시간 운영체제 · 최악 실행 시간 · 꼬리 지연 · 응답 시간 · 용량 계획