평균의 경우

평균의 경우는 알고리즘이 보통 얼마나 걸리는지를 알려 줍니다. 들어올 수 있는 입력마다 드는 일을 셉니다. 그 수들의 평균을 냅니다. 이 평균을 내려면 어떤 입력이 얼마나 자주 오는지를 먼저 가정해야 합니다. 그래서 답은 그 가정에 달려 있습니다.

쉽고 빠른 이해

평균의 경우는 흔히 들어오는 입력에서 알고리즘이 드는 일을 말해 줍니다. 배열에서 값을 앞에서부터 하나씩 찾는다면 찾는 값은 대개 중간쯤에서 나옵니다. 그래서 평균으로는 배열의 절반쯤을 봅니다.

가장 불리한 입력만 보면 자주 쓰는 알고리즘 여럿이 평소보다 훨씬 느려 보입니다. 값을 정렬하는 퀵 정렬이 그렇습니다. 평균의 경우가 있어야 이런 알고리즘이 평소에 얼마나 빠른지를 말할 수 있습니다.

이렇게 셉니다.

1. 어떤 입력이 얼마나 자주 올지 가정합니다
2. 입력마다 드는 일을 셉니다
3. 자주 오는 입력에 무게를 더 실어 평균을 냅니다

가정이 현실과 다르면 평균도 현실과 어긋납니다. 불리한 입력 하나가 오래 걸리지 않는다는 약속도 해 주지 않습니다.

상세

집에서 회사까지 가는 시간은 날마다 다릅니다. 길이 꽉 막히는 날이 있습니다. 텅 빈 날도 있습니다. 누가 보통 얼마나 걸리냐고 물으면 가장 막혔던 날을 대지 않습니다. 여러 날을 떠올려 대충 평균을 댑니다.

평균의 경우는 이 셈을 알고리즘에 옮긴 것입니다. 알고리즘에 들어오는 입력이 얼마나 큰지를 입력 크기 n 으로 적습니다. 배열이라면 원소의 수입니다. 크기가 같은 입력이라도 안에 든 값에 따라 드는 일이 다릅니다.

드는 일은 초로 재지 않고 단계 수로 셉니다. 단계는 값 둘을 견주는 비교 한 번처럼 알고리즘이 되풀이하는 기본 동작입니다. 이렇게 세면 기계가 빠르든 느리든 같은 답이 나옵니다. 크기 n 인 입력마다 단계 수를 세고 그 평균을 낸 것이 평균의 경우입니다.

평균을 내려면 입력마다 얼마나 자주 오는지를 알아야 합니다. 어떤 값이 얼마의 확률로 나오는지 적어 둔 것이 확률 분포입니다. 가장 흔한 가정은 모든 입력이 같은 확률로 온다는 것입니다. 정렬이라면 값이 놓일 수 있는 모든 순서가 똑같이 자주 온다고 봅니다.

확률이 입력마다 다르면 자주 오는 입력에 무게를 더 실어 평균을 냅니다. 입력마다 단계 수에 그 입력의 확률을 곱해 모두 더합니다. 이렇게 낸 평균이 확률에서 말하는 기댓값입니다. 평균의 경우는 단계 수의 기댓값입니다.

가장 오래 걸리는 입력을 기준으로 세는 방식은 최악의 경우입니다. 어떤 입력이 와도 이보다 오래 걸리지 않는다는 약속이라 믿을 만합니다. 하지만 최악의 입력이 드물게만 오는 알고리즘도 많습니다. 그런 알고리즘을 최악의 경우로만 재면 평소 모습과 동떨어진 답이 나옵니다.

퀵 정렬이 그런 알고리즘입니다. 퀵 정렬은 값 하나를 기준으로 골라 그보다 작은 값과 큰 값으로 나눕니다. 이 기준값이 피벗입니다. 나눈 두 쪽에서 같은 일을 되풀이하면 정렬이 끝납니다.

피벗이 매번 가장 작거나 가장 큰 값으로 잡히면 한 번 나눌 때 값이 하나씩만 줄어 아주 느려집니다. 이런 입력은 드뭅니다. 보통은 피벗이 값들을 엇비슷하게 가릅니다. 평균의 경우는 이 보통의 모습을 수로 말해 줍니다.

아래에서는 먼저 선형 탐색 하나로 평균을 직접 셉니다. 가정 하나를 바꾸면 답이 어떻게 달라지는지도 봅니다. 이어서 평균을 최악의 경우와 견주어 평균이 가리는 불리한 입력을 찾습니다. 마지막으로 무작위 알고리즘과 분할 상환 비용이 평균의 경우와 어떻게 다른지 가릅니다.

선형 탐색으로 센 평균

선형 탐색은 배열의 첫 칸부터 하나씩 찾는 값과 견줍니다. 찾는 값이 첫 칸에 있으면 비교 한 번으로 끝납니다. 마지막 칸에 있으면 비교를 n 번 합니다. 찾는 값이 몇 번째 칸에 있느냐가 단계 수를 정합니다.

찾는 값이 배열 안에 꼭 있고 어느 칸에든 같은 확률로 있다고 가정해 봅시다. 칸이 넷인 배열이라면 칸마다 비교 횟수가 이렇게 나옵니다.

넷의 확률이 같으니 비교 횟수를 모두 더해 넷으로 나누면 됩니다. (1+2+3+4)/4 는 2.5 번입니다. 칸이 n 개면 같은 셈으로 (n+1)/2 번이 나옵니다. 배열의 절반쯤을 본다는 뜻입니다.

가정 하나를 바꾼 평균

이번에는 찾는 값이 절반의 확률로 배열에 아예 없다고 가정합니다. 없는 값을 찾을 때는 n 칸을 다 견준 뒤에야 없다는 것을 압니다. 값이 있을 때는 앞 소절과 같이 평균 (n+1)/2 번입니다.

두 경우를 절반씩 섞으면 평균은 (n+1)/4 + n/2, 곧 (3n+1)/4 번입니다. 칸이 넷이면 3.25 번이 됩니다. 알고리즘은 하나도 안 바뀌었습니다. 가정 하나를 바꾸자 평균이 2.5 번에서 3.25 번으로 늘었습니다.

그래서 평균의 경우를 말할 때는 가정을 함께 밝혀야 합니다. 평균으로 이만큼 걸린다는 말 뒤에는 늘 어떤 입력이 온다고 봤는지가 숨어 있습니다.

단계 수가 늘어나는 꼴

빅오 표기법은 입력이 커질 때 단계 수가 어떤 꼴로 늘어나는지만 적는 방법입니다. 앞에서 구한 (n+1)/2 와 (3n+1)/4 는 둘 다 n 에 비례해 늘어납니다. 그래서 둘 다 O(n) 이라고 적습니다. 가정을 바꿔 평균이 늘었어도 늘어나는 꼴은 같습니다.

뒤 절의 표에는 O(n) 말고도 꼴이 셋 더 나옵니다. O(1) 은 n 이 아무리 커져도 단계 수가 일정한 꼴입니다. O(n²) 은 n 이 두 배가 될 때 단계 수가 네 배가 되는 꼴입니다.

남은 하나인 O(n log n) 에는 log n 이 들어 있습니다. log n 은 n 을 2로 몇 번 나눠야 1이 되는지를 세는 수라서 n 이 커져도 아주 천천히 늘어납니다. 그래서 O(n log n) 은 O(n) 보다 단계 수가 조금 더 많이 늘어나는 꼴입니다.

최악·최선의 경우와 견준 평균

최선의 경우는 가장 적게 걸리는 입력을 기준으로 잰 것입니다. 세 경우는 모두 크기 n 인 같은 입력들에서 나옵니다. 입력마다 단계 수를 센 뒤에 무엇을 고르느냐만 다릅니다.

flowchart TD
    A["크기 n 인 입력들"] --> B["입력마다 센 단계 수"]
    B -->|가장 큰 값| C["최악의 경우"]
    B -->|가장 작은 값| D["최선의 경우"]
    B -->|확률로 무게를 실은 평균| E["평균의 경우"]

아래 표에는 해시테이블도 들어갑니다. 해시테이블은 키로 칸 번호를 계산해 그 칸에 값을 넣고 찾는 자료구조입니다. 키들이 여러 칸에 고르게 흩어지면 칸 하나만 보고 값을 찾습니다.

표에서 평균과 최악이 갈리는 줄은 퀵 정렬과 해시테이블입니다. 두 알고리즘의 성능을 흔히 평균의 경우로 말하는 까닭이 여기 있습니다. 선형 탐색처럼 평균과 최악의 꼴이 같으면 평균을 따로 말할 일이 적습니다.

평균이 가리는 불리한 입력

평균의 경우는 가정이 맞을 때만 평소 모습을 알려 줍니다. 퀵 정렬이 늘 맨 앞 값을 피벗으로 고른다고 해 봅시다. 이미 정렬된 배열이 들어오면 피벗이 매번 가장 작은 값이 되어 최악의 경우로 떨어집니다. 정렬된 데이터가 자주 오는 곳에서는 모든 순서가 똑같이 자주 온다는 가정이 깨진 것입니다.

해시테이블도 가정 위에 서 있습니다. 평균 O(1) 은 키가 칸에 고르게 흩어진다는 가정에서 나옵니다. 여러 키가 한 칸에 몰리면 그 칸에 든 키를 하나씩 견줘야 합니다. 모든 키가 한 칸에 몰리면 O(n) 까지 늘어납니다.

입력을 누가 고르는지도 봐야 합니다. 웹 서버가 요청에 실려 온 매개변수 이름을 해시테이블의 키로 담는다고 해 봅시다. 공격자가 한 칸에 몰리는 이름만 골라 보내면 평균의 가정이 일부러 깨집니다. 이런 공격을 해시 플러딩이라고 부릅니다.

무작위로 고르는 알고리즘

입력에 대한 가정에 기대지 않으려고 알고리즘 안에서 무작위를 쓰기도 합니다. 퀵 정렬이 피벗을 무작위로 고르면 이미 정렬된 배열이 와도 한쪽 끝의 피벗이 계속 나올 확률은 아주 작습니다. 스스로 무작위 값을 뽑아 쓰는 알고리즘이 무작위 알고리즘입니다.

이때의 평균은 입력에 대한 평균이 아닙니다. 입력은 무엇이든 하나로 정해 둡니다. 그 입력에서 알고리즘이 뽑는 무작위 값들에 대해 평균을 냅니다.

이 평균을 기대 실행 시간이라고 불러 평균의 경우와 가릅니다. 피벗을 무작위로 고르는 퀵 정렬은 어떤 입력에서도 기대 실행 시간이 O(n log n) 입니다.

해시테이블도 같은 방법을 씁니다. 칸 번호를 계산할 때 무작위 값을 섞어 두면 공격자는 어느 키들이 한 칸에 몰릴지 미리 알 수 없습니다.

분할 상환 비용과 다른 점

분할 상환 비용도 평균과 비슷한 셈을 합니다. 이름의 비용은 앞에서 센 단계 수를 말합니다. 연산을 여러 번 이어서 할 때 드는 단계 수를 모두 더해 횟수로 나눕니다. 나눈 값이 연산 한 번의 몫입니다.

이 셈에는 입력에 대한 가정이 없습니다. 합계를 가장 불리한 입력으로 재기 때문입니다. 그래서 어떤 입력이 오든 연산을 k 번 한 단계 수의 합은 k 에 그 몫을 곱한 값을 넘지 않습니다.

평균의 경우는 반대로 가정에서 출발합니다. 가정이 맞을 때 연산 한 번에 평균 얼마가 드는지를 말합니다. 해시테이블에서 키를 찾는 일이 평균 O(1) 인 것은 평균의 경우입니다.

해시테이블에 키를 계속 넣으면 칸이 모자라 칸 수를 늘려야 할 때가 옵니다. 칸 수를 늘리면 이미 든 키를 모두 새 칸 번호로 다시 계산해 옮겨야 해서 그 한 번이 크게 듭니다. 이 큰 한 번은 드물게 옵니다. 그 단계 수를 여러 번의 넣기에 나눠 세는 것이 분할 상환 비용입니다.

관련 항목

평균의 경우와 나란히 서는 분석 기준

최악의 경우 · 최선의 경우 · 분할 상환 비용 · 기대 실행 시간 · 평활 분석

평균의 경우를 적는 복잡도 잣대

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

평균을 내는 데 쓰는 확률 개념

평균 · 확률 분포 · 균등 분포 · 기댓값 · 확률 변수 · 무작위 순열

평균의 경우로 성능을 말하는 알고리즘과 자료구조

퀵 정렬 · 퀵 선택 · 해시테이블 · 선형 탐색 · 이진 탐색 트리 · 삽입 정렬 · 버킷 정렬

평균의 경우가 기대는 가정을 깨는 공격과 지키는 기법

해시 플러딩 · 해시 충돌 · 서비스 거부 공격 · 무작위 알고리즘 · 피벗 · 유니버설 해싱