06. 알고리즘, 함수의 증가, 알고리즘의 복잡도

알고리즘을 이해하려면 무엇을 계산하는지뿐 아니라 왜 맞는지, 입력이 커질 때 얼마나 많은 일을 하는지도 봐야 한다. 검색과 정렬을 직접 따라가고, 반복 횟수를 함수로 표현하면 빅오 표기법이 무엇을 설명하는지 분명해진다. 특히 알고리즘 하나가 느리다는 사실과 문제 자체가 어렵다는 주장은 구별해야 한다.

연습문제로 바로 가기 · 먼저 풀어 본 뒤 각 문제의 해설 보기를 눌러 확인할 수 있다.

1. 알고리즘의 조건과 최댓값 찾기

알고리즘은 문제를 해결하기 위한 명확한 명령들의 유한한 기술이다. 입력과 출력이 정해져 있어야 하고, 각 단계가 정확히 정의되어야 한다. 올바른 입력에서 정답을 내는 정확성, 유한한 단계 안에 끝나는 유한성, 각 단계를 실제로 수행할 수 있는 효과성, 특정 사례에만 한정되지 않는 일반성도 필요하다. 효과성은 “아주 빠르다”는 뜻이 아니라 기본 단계를 유한한 시간에 실행할 수 있다는 뜻이다.

길이가 n≥1n\ge1인 정수열의 최댓값은 다음과 같이 찾는다. 의사코드의 배열 인덱스는 1부터 시작한다.

maximum(a[1..n]):
    best := a[1]
    for i := 2 to n:
        if best < a[i]:
            best := a[i]
    return best

8,4,11,3,108,4,11,3,10에서는 best가 8,8,11,11,118,8,11,11,11로 변한다. 5,1,8,35,1,8,3에서는 5,5,8,85,5,8,8이다. ii번째 원소까지 처리한 뒤 best가 앞의 ii개 원소의 최댓값이라는 성질이 유지된다. 처음에는 원소 하나에서 참이고, 다음 원소와 비교해 더 큰 값을 남기므로 끝까지 유지된다. 종료 시 전체의 최댓값이 나온다.

원소끼리의 비교만 세면 n−1n-1회다. 반복 조건 검사까지 비교로 세면 n+(n−1)=2n−1n+(n-1)=2n-1회다. 정확한 횟수는 계산 기준에 따라 달라져도 선형으로 증가한다는 사실은 같다.

2. 순차 검색과 이진 검색

순차 검색

linear_search(x, a[1..n]):
    i := 1
    while i <= n and x != a[i]:
        i := i + 1
    if i <= n:
        return i
    return 0

and는 앞 조건이 거짓이면 뒤를 평가하지 않는 단락 평가로 읽는다. 따라서 범위 밖의 원소를 접근하지 않는다. 정렬되지 않은 배열에서도 사용할 수 있다.

xx가 ii번째 위치에 있을 때 원소와의 비교는 ii회다. 반복 조건의 두 비교와 마지막 if까지 세면 2i+12i+1회다. 없을 때는 전체 nn개를 확인하고 종료하며 2n+22n+2회다. 따라서 최악 시간은 Θ(n)\Theta(n)이다.

찾는 값이 반드시 존재하고 각 위치에 있을 확률이 같다면 평균 비교 횟수는

1n∑i=1n(2i+1)=n(n+1)+nn=n+2.\frac1n\sum_{i=1}^{n}(2i+1) =\frac{n(n+1)+n}{n}=n+2.

원소와의 비교만 세면 (n+1)/2(n+1)/2회다. 어느 기준이든 평균은 Θ(n)\Theta(n)이며, 평균을 말할 때는 이러한 확률 가정이 필요하다.

이진 검색

이진 검색은 입력이 오름차순으로 정렬되어 있다는 조건을 사용한다.

binary_search(x, a[1..n]):
    if n = 0:
        return 0
    i := 1
    j := n
    while i < j:
        m := floor((i + j) / 2)
        if x > a[m]:
            i := m + 1
        else:
            j := m
    if x = a[i]:
        return i
    return 0

x>a[m]x>a[m]이면 정렬 순서에 의해 mm 이하의 위치에는 답이 없다. 그렇지 않으면 mm보다 뒤에는 더 큰 값만 있으므로 오른쪽 끝을 mm으로 줄인다. 답이 있다면 항상 현재 구간 안에 남는다는 성질을 유지하면서 구간을 절반 정도로 줄인다.

배열 1,2,3,5,6,7,8,10,12,13,15,16,18,19,20,221,2,3,5,6,7,8,10,12,13,15,16,18,19,20,22에서 19를 찾으면 다음과 같다.

iijjmma[m]a[m]다음 구간
116810[9,16][9,16]
9161216[13,16][13,16]
13161419[13,14][13,14]
13141318[14,14][14,14]

마지막 원소가 19이므로 위치 14를 반환한다. 반면 1,3,5,7,9,11,13,151,3,5,7,9,11,13,15에서 4를 찾으면 구간이 [1,8]→[1,4]→[3,4]→[3,3][1,8]\to[1,4]\to[3,4]\to[3,3]으로 줄고 마지막 값 5가 4와 달라 0을 반환한다.

n=2kn=2^k이면 반복이 kk번이고, 각 반복의 조건과 원소 비교를 두 번으로 세면 종료 검사와 마지막 동등 비교를 포함해 2k+22k+2회다. 일반적인 n≥1n\ge1에서는 최대 2⌈log⁡2n⌉+22\lceil\log_2n\rceil+2회로, 최악 복잡도는 Θ(log⁡n)\Theta(\log n)이다. n=106n=10^6이면 이 기준에서 최대 42회다. 다만 정렬되지 않은 데이터라면 정렬에 드는 비용도 별도로 고려해야 한다.

3. 버블 정렬과 삽입 정렬

버블 정렬

인접한 두 원소가 잘못된 순서이면 바꾼다. 한 번 훑으면 아직 정렬되지 않은 부분의 최댓값이 뒤로 이동한다.

bubble_sort(a[1..n]):
    for i := 1 to n - 1:
        for j := 1 to n - i:
            if a[j] > a[j + 1]:
                swap(a[j], a[j + 1])

5,2,4,6,15,2,4,6,1을 정렬하면

단계배열
시작5,2,4,6,15,2,4,6,1
1회전2,4,5,1,62,4,5,1,6
2회전2,4,1,5,62,4,1,5,6
3회전2,1,4,5,62,1,4,5,6
4회전1,2,4,5,61,2,4,5,6

원소 비교 수는

(n−1)+(n−2)+⋯+1=n(n−1)2.(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}2.

위 구현은 교환이 없는 회전에서도 끝까지 실행하므로 이미 정렬된 입력에도 같은 횟수로 비교한다. n=10n=10이면 45회이고 복잡도는 Θ(n2)\Theta(n^2)다. 교환이 없으면 종료하는 최적화를 넣은 버전은 최선 경우가 달라진다.

삽입 정렬

앞부분이 정렬되어 있다고 유지하면서 다음 원소를 그 안의 올바른 자리에 넣는다. 여기서는 삽입 위치를 앞에서부터 찾는 버전을 사용한다.

insertion_sort(a[1..n]):
    for j := 2 to n:
        i := 1
        while a[j] > a[i]:
            i := i + 1
        value := a[j]
        for k := j down to i + 1:
            a[k] := a[k - 1]
        a[i] := value

i=ji=j가 되면 자기 자신과 비교하여 조건이 거짓이므로 탐색이 끝난다. 삽입할 값을 따로 저장한 뒤 원소들을 오른쪽으로 옮겨야 값이 덮어써지지 않는다.

단계배열
시작5,2,4,6,15,2,4,6,1
j=2j=22,5,4,6,12,5,4,6,1
j=3j=32,4,5,6,12,4,5,6,1
j=4j=42,4,5,6,12,4,5,6,1
j=5j=51,2,4,5,61,2,4,5,6

이 버전에서 jj번째 원소의 삽입 위치를 찾는 비교는 최대 jj회이므로 총 2+3+⋯+n=n(n+1)/2−12+3+\cdots+n=n(n+1)/2-1회다. n=10n=10이면 최대 54회다. 이미 정렬된 입력은 앞에서 끝까지 탐색하므로 비교가 많고, 역순 입력은 삽입 위치는 빨리 찾지만 이동이 많다. 어느 쪽이든 전체 작업량은 이 구현에서 이차적으로 커질 수 있다.

흔히 사용하는 뒤에서부터 탐색하는 삽입 정렬은 이미 정렬된 입력에서 Θ(n)\Theta(n)이다. “삽입 정렬”이라는 이름만 보고 정확한 비교 횟수나 최선 경우를 정하지 말고 구현과 세는 연산을 확인해야 한다. 두 방식 모두 최악 시간은 Θ(n2)\Theta(n^2)다.

4. 문자열 매칭

길이 nn인 텍스트 TT에서 길이 mm인 패턴 PP를 찾는다. 이동량 ss는 패턴을 오른쪽으로 몇 글자 옮겼는지 나타내며 시작 위치는 s+1s+1이다.

string_match(T[1..n], P[1..m]):
    for s := 0 to n - m:
        j := 1
        while j <= m and T[s + j] = P[j]:
            j := j + 1
        if j > m:
            output s

1≤m≤n1\le m\le n을 가정한다. 검사할 이동은 n−m+1n-m+1개이며, 각 이동에서 최대 mm글자를 비교하므로 최악 문자 비교 횟수는 (n−m+1)m(n-m+1)m이다.

텍스트패턴유효한 이동 ss시작 위치
eceyeyeeye2, 43, 5
1100101110145
CATCACAGAGACAG56

마지막 예는 텍스트 길이 11, 패턴 길이 3이라 총 9개 이동을 검사한다. 패턴이 겹쳐 나타날 수 있으므로 성공한 뒤에도 모든 이동을 계속 확인한다.

5. 탐욕 알고리즘과 최적성

탐욕 알고리즘은 각 단계에서 당장 유리한 선택을 한다. 선택이 간단하다는 사실만으로 최적해를 보장하지는 않는다.

거스름돈

큰 액면부터 남은 금액을 넘지 않는 동전을 선택한다.

change(coins in descending order, amount):
    for coin in coins:
        count[coin] := 0
        while amount >= coin:
            count[coin] := count[coin] + 1
            amount := amount - coin
    return count, amount

마지막 나머지가 0이어야 정확하게 거슬러 준 것이다. 액면 1이 있으면 모든 음이 아닌 정수 금액을 만들 수 있다. 액면이 25,10,5,125,10,5,1이면 67은 25+25+10+5+1+125+25+10+5+1+1로 6개, 41은 25+10+5+125+10+5+1로 4개다.

이 액면 조합의 최적성은 교환 논증으로 보일 수 있다. 최소 동전 해에는 1짜리가 다섯 개 이상 있을 수 없다. 5짜리 하나로 바꾸면 동전 수가 줄기 때문이다. 같은 이유로 5짜리는 최대 하나, 10짜리는 최대 둘이며, 10짜리 둘과 5짜리 하나를 동시에 가질 수 없다. 이를 합치면 25보다 작은 동전들의 총액은 최대 24다.

따라서 최소 해의 25짜리 개수는 탐욕 방식의 ⌊n/25⌋\lfloor n/25\rfloor와 같아야 한다. 더 적으면 작은 동전으로 25 이상을 채워야 해서 앞의 성질과 모순이다. 나머지에서도 5·1짜리로 만들 수 있는 최적 해의 총액은 9 이하이고 1짜리는 4 이하이므로, 10·5·1짜리 개수도 차례로 탐욕 선택과 같아진다.

액면 5가 빠지면 논증은 성립하지 않는다. 25,10,125,10,1로 30을 만들 때 탐욕 방식은 25와 1 다섯 개, 총 6개지만 10 세 개면 된다. 31도 탐욕은 7개, 10+10+10+110+10+10+1은 4개다.

겹치지 않는 일정의 최대 개수

한 장소에서 시간 구간이 겹치지 않는 일정을 최대한 많이 선택한다. 끝나는 시각과 다음 시작 시각이 같은 것은 허용한다. 이 문제에서는 종료 시각이 가장 이른 일정부터 선택한다.

schedule(talks):
    sort talks by finish time
    selected := empty list
    last_finish := -infinity
    for talk in talks:
        if talk.start >= last_finish:
            append talk to selected
            last_finish := talk.finish
    return selected

최적 해의 첫 일정 oo보다 탐욕이 고른 첫 일정 gg가 늦게 끝나지는 않는다. 따라서 최적 해에서 oo를 gg로 바꾸어도 뒤의 일정들과 겹치지 않고 개수도 같다. 첫 선택을 탐욕 선택과 맞춘 뒤 남은 일정에 같은 논증을 반복하면 최적성이 따라온다.

가장 일찍 시작하는 기준은 [8,12],[9,10],[10,11][8,12],[9,10],[10,11]에서 실패한다. 처음 구간을 고르면 하나뿐이지만 나머지 둘을 고를 수 있다. 가장 짧은 기준도 [8:00,9:15][8{:}00,9{:}15], [9:00,10:00][9{:}00,10{:}00], [9:45,11:00][9{:}45,11{:}00]에서 가운데 하나만 고르게 된다. 첫째와 셋째를 고르면 두 개다.

6. 정지 문제

임의의 프로그램 PP와 입력 II에 대해 실행이 언젠가 멈추는지 항상 정확하게 판정하고 종료하는 알고리즘 H(P,I)H(P,I)가 있다고 가정하자. 다음 프로그램을 만든다.

K(P):
    if H(P, P) says "halts":
        loop forever
    else:
        halt

프로그램을 문자열로 표현할 수 있으므로 자기 자신을 입력으로 줄 수 있다. 이제 K(K)K(K)를 생각한다. H(K,K)H(K,K)가 멈춘다고 판정하면 정의에 의해 무한 반복하고, 멈추지 않는다고 판정하면 즉시 멈춘다. 어느 경우든 판정과 모순이다.

따라서 모든 프로그램과 입력을 처리하는 그런 판정기는 존재하지 않는다. 특정 프로그램의 종료를 분석할 수 없다는 뜻이 아니라, 모든 경우에 성공하는 일반 알고리즘이 없다는 뜻이다. 이는 단지 시간이 오래 걸린다는 복잡도 문제와 다르다.

7. 빅오의 정의와 증인

실행 시간을 기계에 종속된 초 단위로만 비교하는 대신, 입력 크기 nn에 따른 기본 연산 횟수를 비교한다. 100n2+17n+4100n^2+17n+4와 n3n^3은 작은 nn에서 전자가 더 크지만, 충분히 큰 nn에서는 후자가 더 커진다.

f(n)=O(g(n))  ⟺  ∃C>0 ∃n0 ∀n>n0,∣f(n)∣≤C∣g(n)∣.f(n)=O(g(n)) \iff \exists C>0\ \exists n_0\ \forall n>n_0, \quad |f(n)|\le C|g(n)|.

C,n0C,n_0를 증인이라고 한다. 둘은 nn과 무관한 상수여야 한다. 빅오는 상수배를 허용한 점근적 상한이다. 항상 엄격히 느리게 자란다는 뜻은 아니며 같은 차수여도 포함된다. 엄밀히 O(g)O(g)는 함수들의 집합이므로 f∈O(g)f\in O(g)가 정확한 표기이고, 등호는 관례다.

증인 찾기

n>1n>1이면 n≤n2n\le n^2, 1≤n21\le n^2이므로

n2+2n+1≤4n2.n^2+2n+1\le4n^2.

따라서 C=4,n0=1C=4,n_0=1이 증인이다. n>2n>2에서 2n≤n22n\le n^2을 사용하면 C=3,n0=2C=3,n_0=2도 가능하다. 증인은 유일하지 않다.

주장가능한 증인부등식의 근거
5n3=O(n4)5n^3=O(n^4)C=5,n0=1C=5,n_0=1n3≤n4n^3\le n^4
3n2+5n+2=O(n2)3n^2+5n+2=O(n^2)C=10,n0=1C=10,n_0=1각 항을 n2n^2의 배수로 제한
7n2=O(n3)7n^2=O(n^3)C=1,n0=7C=1,n_0=77<n7<n
7n4−3n2+6=O(n4)7n^4-3n^2+6=O(n^4)C=16,n0=1C=16,n_0=1절댓값과 삼각부등식

더 큰 함수로 상한을 잡을 수도 있어서 n2=O(n3)n^2=O(n^3)은 참이다. 하지만 정확한 증가 차수를 말할 때는 가능한 한 밀접한 상한을 쓰는 것이 유용하다.

빅오가 아님을 증명하기

n2=O(n)n^2=O(n)이라고 가정하면 충분히 큰 모든 nn에서 n2≤Cnn^2\le Cn, 즉 n≤Cn\le C여야 한다. n>max⁡(n0,C)n>\max(n_0,C)를 선택하면 모순이다. 마찬가지로 n3≤C⋅7n2n^3\le C\cdot7n^2는 n≤7Cn\le7C를 요구하므로 n3n^3은 O(7n2)O(7n^2)가 아니다.

몇 개의 수치만으로 불성립을 증명할 수는 없다. 2n2^n이 O(n2)O(n^2)가 아님은 비율로 보일 수 있다. rn=2n/n2r_n=2^n/n^2이면

rn+1rn=2(nn+1)2≥3225>1(n≥4).\frac{r_{n+1}}{r_n}=2\left(\frac n{n+1}\right)^2\ge\frac{32}{25}>1\quad(n\ge4).

따라서 rnr_n은 일정 비율 이상으로 계속 증가해 어떤 상수보다도 커진다.

8. 함수의 증가와 결합

다항식 f(x)=adxd+⋯+a0f(x)=a_dx^d+\cdots+a_0에서 x>1x>1이면

∣f(x)∣≤∑i=0d∣ai∣xi≤(∑i=0d∣ai∣)xd.|f(x)|\le\sum_{i=0}^{d}|a_i|x^i \le\left(\sum_{i=0}^{d}|a_i|\right)x^d.

따라서 O(xd)O(x^d)다. 최고차항의 계수가 0이 아니면 f(x)/xd→ad≠0f(x)/x^d\to a_d\ne0이므로 하한도 같은 차수로 얻는다.

다음과 같은 간단한 제한도 유용하다.

∑k=1nk≤n2,∑k=1nk2≤n3,n!≤nn,log⁡(n!)≤nlog⁡n.\sum_{k=1}^{n}k\le n^2,\quad \sum_{k=1}^{n}k^2\le n^3,\quad n!\le n^n,\quad \log(n!)\le n\log n.

로그는 밑이 1보다 큰 고정 상수라고 가정한다. 밑 변환 공식 log⁡bn=log⁡an/log⁡ab\log_bn=\log_an/\log_ab에 따라 밑이 달라도 상수배 차이이므로 같은 점근적 차수다.

증가 차수는 대체로 다음 순서다. 이것은 모든 작은 nn에서의 값의 대소관계가 아니라 충분히 큰 nn에서의 증가율 비교다.

1≺log⁡n≺n≺nlog⁡n≺n2≺2n≺n!.1\prec\log n\prec n\prec n\log n\prec n^2\prec2^n\prec n!.

고정된 양수 c,dc,d와 b>1b>1에 대해 (log⁡n)c(\log n)^c는 ndn^d보다, ndn^d는 bnb^n보다 느리게 증가한다. 1<b<c1<b<c이면 bnb^n은 cnc^n보다 느리고, 고정된 cnc^n은 계승보다 느리다.

예를 들어 증가 순서는

(log⁡n)2≺8n≺2nlog⁡n≺n2≺1.1n≺n!(\log n)^2\prec8\sqrt n\prec2n\log n\prec n^2\prec1.1^n\prec n!

이다. 조금 더 복잡한 목록도 차수를 묶어서 정리할 수 있다.

  1. 상수 1000010000
  2. log⁡log⁡n\log\log n
  3. (log⁡n)2(\log n)^2
  4. n2(log⁡n)3n^2(\log n)^3
  5. 8n3+17n2+1118n^3+17n^2+111과 n3+n(log⁡n)2n^3+n(\log n)^2: 둘 다 Θ(n3)\Theta(n^3)
  6. 1.5n1.5^n
  7. 2n2^n
  8. 2n(n2+1)2^n(n^2+1)
  9. n!n!

합과 곱의 빅오

f1=O(g1)f_1=O(g_1), f2=O(g2)f_2=O(g_2)이면

f1+f2=O(max⁡(∣g1∣,∣g2∣)),f1f2=O(g1g2).f_1+f_2=O(\max(|g_1|,|g_2|)),\qquad f_1f_2=O(g_1g_2).

공통 시작점 이후에 ∣fi∣≤Ci∣gi∣|f_i|\le C_i|g_i|를 적용한다. 합에는 삼각부등식과 C1+C2C_1+C_2, 곱에는 C1C2C_1C_2를 사용하면 된다. 합에서 상쇄가 생길 수 있으므로 이 규칙은 우선 상한에 대한 규칙이다.

3nlog⁡(n!)+(n2+3)log⁡n=O(n2log⁡n)3n\log(n!)+(n^2+3)\log n=O(n^2\log n)

인 것은 각 항이 그 차수로 제한되기 때문이다. 또

(x+1)log⁡(x2+1)+3x2=O(x2)(x+1)\log(x^2+1)+3x^2=O(x^2)

이다. 앞부분은 O(xlog⁡x)O(x\log x)이고, 뒷부분은 O(x2)O(x^2)다. 3x+5x23x+5x^2는 O(x2)O(x^2), (3x)(5x2)(3x)(5x^2)는 O(x3)O(x^3)이며, 2x3+3x2log⁡x+1002x^3+3x^2\log x+100은 O(x3)O(x^3)이다.

9. 오메가와 세타

f(n)=Ω(g(n))  ⟺  ∃c>0 ∃n0 ∀n>n0,∣f(n)∣≥c∣g(n)∣.f(n)=\Omega(g(n)) \iff\exists c>0\ \exists n_0\ \forall n>n_0, \quad|f(n)|\ge c|g(n)|.

오메가는 하한이다. 세타는 상한과 하한이 동시에 성립하는 경우다.

f(n)=Θ(g(n))  ⟺  ∃c1,c2>0 ∃n0 ∀n>n0,c1∣g(n)∣≤∣f(n)∣≤c2∣g(n)∣.f(n)=\Theta(g(n)) \iff \exists c_1,c_2>0\ \exists n_0\ \forall n>n_0, \quad c_1|g(n)|\le|f(n)|\le c_2|g(n)|.

n>1n>1에서 4n2≤4n2+3n≤7n24n^2\le4n^2+3n\le7n^2이므로 4n2+3n=Θ(n2)4n^2+3n=\Theta(n^2)다. 8x3+5x2+7≥8x38x^3+5x^2+7\ge8x^3이므로 Ω(x3)\Omega(x^3)이고, 다항식 상한까지 합치면 Θ(x3)\Theta(x^3)다.

n22≤n(n+1)2≤n2(n≥1)\frac{n^2}{2}\le\frac{n(n+1)}2\le n^2\quad(n\ge1)

이므로 1+⋯+n=Θ(n2)1+\cdots+n=\Theta(n^2)다. 3x2+8xlog⁡x3x^2+8x\log x도 Θ(x2)\Theta(x^2)다. x>1x>1에서 x3+2x+1≤4x3x^3+2x+1\le4x^3이므로 x3=Ω(x3+2x+1)x^3=\Omega(x^3+2x+1)도 성립한다.

최고차항이 0이 아닌 다항식은 절댓값을 사용하는 정의에서 최고차항의 차수와 같은 세타다. 따라서 3x8+10x7+221x2+14443x^8+10x^7+221x^2+1444는 Θ(x8)\Theta(x^8), x19−18x4−10112x^{19}-18x^4-10112는 Θ(x19)\Theta(x^{19}), −x99+40001x98+100003x-x^{99}+40001x^{98}+100003x는 Θ(x99)\Theta(x^{99})다.

빅오가 최악, 오메가가 최선이라는 뜻은 아니다. 먼저 최악·평균·최선 중 어떤 실행 비용 함수를 분석할지 정하고, 그 함수의 상한·하한·차수를 각각 O,Ω,ΘO,\Omega,\Theta로 표현한다.

10. 행렬 계산과 연산 횟수

시간 복잡도는 연산 횟수, 공간 복잡도는 사용하는 메모리의 양이다. 최악 경우는 크기가 같은 유효 입력 중 연산이 가장 많은 경우이고, 최선 경우는 가장 적은 경우다. 평균 경우는 입력의 확률분포에 따른 연산 횟수의 기댓값이다. 아래의 행렬 계산에서는 성분 하나의 덧셈과 곱셈을 상수 비용으로 가정한다. 정수의 비트 길이가 커지는 경우에는 그 산술 연산의 비용도 별도로 고려해야 한다.

matrix_product(A[m,k], B[k,n]):
    for i := 1 to m:
        for j := 1 to n:
            C[i,j] := 0
            for q := 1 to k:
                C[i,j] := C[i,j] + A[i,q] * B[q,j]
    return C

결과 성분이 mnmn개이고 각각 kk번 곱하므로 곱셈은 mknmkn회다. 위 코드 그대로면 0에 첫 항을 더하는 것까지 성분당 kk회 덧셈을 한다. 첫 곱을 초기값으로 놓는 구현에서는 성분당 k−1k-1회로 줄어든다. 두 n×nn\times n 행렬을 정의대로 곱하는 알고리즘은 어느 방식이든 Θ(n3)\Theta(n^3)이다.

불 곱은 갱신을 C[i,j] := C[i,j] OR (A[i,q] AND B[q,j])로 바꾼다. 단락 최적화 없이 모두 계산하면 정사각행렬에서 AND n3n^3회, OR n3n^3회, 총 2n32n^3회다. 일반 행렬곱에는 스트라센 알고리즘처럼 O(nlog⁡27)O(n^{\log_2 7})에 계산하는 방법도 있으므로, 정의대로 계산한 알고리즘의 비용을 모든 알고리즘의 하한으로 해석하면 안 된다.

행렬 연쇄 곱셈

행렬곱의 결합법칙은 괄호를 바꾸어도 결과가 같다는 뜻이다. 행렬 자체의 순서를 바꾸어도 된다는 뜻은 아니다. 괄호에 따라 중간 행렬의 크기와 연산량은 달라진다.

A1A_1: 30×20, A2A_2: 20×40, A3A_3: 40×10이면

A1(A2A3):20⋅40⋅10+30⋅20⋅10=14000,(A1A2)A3:30⋅20⋅40+30⋅40⋅10=36000.\begin{aligned} A_1(A_2A_3)&:\quad20\cdot40\cdot10+30\cdot20\cdot10=14000,\\ (A_1A_2)A_3&:\quad30\cdot20\cdot40+30\cdot40\cdot10=36000. \end{aligned}

10×100, 100×5, 5×50인 경우에는 반대쪽 괄호가 유리하다.

(A1A2)A3:10⋅100⋅5+10⋅5⋅50=7500,A1(A2A3):100⋅5⋅50+10⋅100⋅50=75000.\begin{aligned} (A_1A_2)A_3&:\quad10\cdot100\cdot5+10\cdot5\cdot50=7500,\\ A_1(A_2A_3)&:\quad100\cdot5\cdot50+10\cdot100\cdot50=75000. \end{aligned}

11. 브루트포스와 문제의 복잡도

브루트포스는 정의에 따라 후보를 직접 검사하는 접근이다. 모든 점 쌍 중 가장 가까운 쌍을 찾는다면

closest_pair(points[1..n]):
    best := infinity
    for i := 2 to n:
        for j := 1 to i - 1:
            d := (x[i] - x[j])^2 + (y[i] - y[j])^2
            if d < best:
                best := d
                answer := (i, j)
    return answer

로 계산한다(n≥2n\ge2). 거리는 음수가 아니고 제곱근은 증가함수이므로 거리의 제곱만 비교해도 된다. 검사하는 쌍은 n(n−1)/2n(n-1)/2개여서 Θ(n2)\Theta(n^2)다. 점이 1,000개이면 499,500쌍이다.

알고리즘 설계에는 탐욕과 브루트포스 외에도 문제를 나누는 분할정복, 겹치는 부분문제의 결과를 저장하는 동적 계획법, 불가능한 후보를 일찍 버리는 백트래킹, 무작위 선택을 사용하는 확률적 방법 등이 있다.

차수이름예시
Θ(1)\Theta(1)상수입력 크기와 무관한 고정 개수의 원소 검사
Θ(log⁡n)\Theta(\log n)로그정렬된 배열의 이진 검색, 최악 경우
Θ(n)\Theta(n)선형최댓값 찾기, 순차 검색의 최악 경우
Θ(nlog⁡n)\Theta(n\log n)선형로그병합 정렬의 비교·병합 작업
Θ(n2)\Theta(n^2)이차기본 버블 정렬, 모든 점 쌍 검사
Θ(n3)\Theta(n^3)삼차정의에 따른 정사각행렬 곱셈
2n2^n개 후보지수적 탐색 공간nn개 명제변수의 모든 진리값 할당
n!n!개 후보계승적 탐색 공간nn개 대상의 모든 순열

후보 개수와 전체 시간은 다를 수 있다. 예를 들어 SAT의 모든 할당이 2n2^n개여도 각 할당에서 식을 검사하는 비용이 추가된다.

P, NP, NP-완전의 구별

결정 문제는 답이 예 또는 아니오인 문제다. P는 입력의 표현 길이에 대해 결정적 다항 시간에 풀 수 있는 결정 문제들의 클래스다. NP는 답이 예인 입력에 대해 다항 길이의 증명서가 존재하고, 그 증명서를 다항 시간에 검증할 수 있는 결정 문제들의 클래스다. NP는 “다항 시간에 풀 수 없는 문제”의 약자가 아니다. P⊆NPP\subseteq NP다.

NP-완전은 NP에 속하면서, NP의 모든 문제가 다항 시간 환원으로 그 문제에 옮겨지는 경우다. 따라서 NP-완전 문제 하나에 다항 시간 알고리즘이 있으면 P=NPP=NP가 된다. SAT는 대표적인 NP-완전 문제다. 진리값 할당을 받으면 식이 참인지 빠르게 확인할 수 있다는 점과, 만족하는 할당을 찾아야 한다는 점을 구별한다.

단순한 완전 탐색이 지수 시간이라는 사실만으로 문제 자체가 다항 시간에 풀리지 않는다고 증명한 것은 아니다. 또한 다항 시간이라는 이론적 분류가 실용적으로 빠르다는 보장은 아니다. n100n^{100}도 다항식이고, 큰 상수와 메모리 비용이 실행을 어렵게 만들 수 있다. 반대로 어려운 최적화 문제에서도 특정 입력의 구조, 근사 알고리즘, 휴리스틱이 유용할 수 있다.

증가율을 시간으로 바꾸어 보기

기본 연산 하나가 가정상 10−1110^{-11}초이고 정확히 f(n)f(n)번 실행된다고 놓자. n=106n=10^6에서 nn번이면 10−510^{-5}초, n2n^2번이면 10초다. n=100n=100에서 2n2^n번이면 약 4.0×10114.0\times10^{11}년이다. 이 숫자는 실제 장비의 측정값이 아니라 증가율의 차이를 보기 위한 계산이다. Θ\Theta 표기만으로는 상수와 실제 연산 비용을 알 수 없으므로 그대로 실행 시간을 예측할 수 없다.

12. 연습문제

문제를 읽고 풀이를 적어 본 뒤 해설을 펼쳐 비교해 보자. 계산 결과뿐 아니라 사용한 정의와 추론 근거까지 설명하는 연습을 한다.

01. 알고리즘의 성질과 최댓값

  1. 알고리즘의 일곱 가지 성질을 쓰자. “유한 단계 안에 끝남”, “각 단계가 정확히 정해짐”은 각각 무엇인가?
  2. 5,1,8,35,1,8,3에 최댓값 알고리즘을 적용할 때 변수 max의 변화를 쓰자.
해설 보기
  1. 입력, 출력, 명확성, 정확성, 유한성, 효과성, 일반성이다. 유한 단계 안에 끝남은 유한성, 각 단계가 정확히 정해짐은 명확성이다. 효과성은 각 단계를 정확하게 유한 시간에 수행할 수 있다는 조건이고, 일반성은 특정 입력 하나에만 맞춘 절차가 아니라 지정한 종류의 입력 전체를 다룬다는 조건이다.
  2. 첫 값으로 초기화한 뒤 5→5→8→85\to5\to8\to8이다. 1은 현재 최댓값보다 작아 유지하고, 8에서 갱신하며, 3에서는 유지한다. 최종 출력은 8이다.

02. 이진 검색 추적

이진 검색은 i=1,j=ni=1,j=n, m=⌊(i+j)/2⌋m=\lfloor(i+j)/2\rfloor에서 x>amx>a_m이면 i=m+1i=m+1, 아니면 j=mj=m으로 줄인다. i=ji=j가 되면 마지막 원소와 비교한다.

  1. 2,4,6,8,10,12,142,4,6,8,10,12,14에서 x=10x=10을 찾을 때 첫 비교와 다음 구간은?
  2. 1,3,5,7,9,11,13,151,3,5,7,9,11,13,15에서 x=4x=4를 찾는 전 과정을 쓰자.
  3. 순차 검색과 이진 검색의 입력 전제는 어떻게 다른가?
해설 보기
  1. (i,j,m)=(1,7,4)(i,j,m)=(1,7,4)이고 a4=8a_4=8. 10>810>8이므로 다음 구간은 [5,7][5,7], 즉 10,12,1410,12,14다.
  2. 과정을 표로 쓰면 다음과 같다.
iijjmmama_m갱신
18474>74>7이 아니므로 j=4j=4
14234>34>3이므로 i=3i=3
34354>54>5가 아니므로 j=3j=3

i=j=3i=j=3에서 a3=5≠4a_3=5\ne4이므로 없음을 뜻하는 0을 반환한다. 3. 순차 검색은 정렬되지 않아도 가능하다. 이진 검색은 비교한 위치를 기준으로 한쪽을 버릴 수 있도록 정렬되어 있어야 한다.

03. 버블 정렬과 삽입 정렬의 단계

리스트 5,2,4,6,15,2,4,6,1에 버블 정렬과 삽입 정렬을 적용하자. 버블 정렬은 왼쪽부터 인접 원소를 비교하여 큰 값을 오른쪽으로 옮기며, 삽입 정렬은 정렬된 앞부분에 다음 값을 삽입한다.

해설 보기

버블 정렬은 한 회전마다 미정렬 부분의 최댓값을 끝에 보낸다.

단계배열
시작5,2,4,6,15,2,4,6,1
1회전2,4,5,1,62,4,5,1,6
2회전2,4,1,5,62,4,1,5,6
3회전2,1,4,5,62,1,4,5,6
4회전1,2,4,5,61,2,4,5,6

삽입 정렬에서는 다음 원소가 들어갈 위치를 찾고 그 뒤의 원소들을 한 칸씩 옮긴다.

삽입할 값삽입 후 배열
22,5,4,6,12,5,4,6,1
42,4,5,6,12,4,5,6,1
62,4,5,6,12,4,5,6,1
11,2,4,5,61,2,4,5,6

6을 넣는 단계에서는 이미 제자리에 있어서 배열이 그대로다.

04. 문자열 매칭의 이동량

이동량 ss는 0부터 세고, 시작 위치는 s+1s+1이다.

  1. 텍스트 11001011에서 패턴 101이 일치하는 모든 이동량을 구하자.
  2. 텍스트 CATCACAGAGA에서 패턴 CAG의 이동량과 단순 매칭이 검사하는 후보 수를 구하자.
해설 보기
  1. s=0,1,2,3,4,5s=0,1,2,3,4,5에서 길이 3 부분문자열은 차례로 110, 100, 001, 010, 101, 011이다. 따라서 s=4s=4만 일치하며 시작 위치는 5다.
  2. s=0s=0부터 8까지 부분문자열은 CAT, ATC, TCA, CAC, ACA, CAG, AGA, GAG, AGA다. s=5s=5에서만 일치한다. 텍스트 길이 11, 패턴 길이 3이므로 후보 수는 11−3+1=911-3+1=9다. 후보 수와 문자 비교의 총횟수는 다른 양이다.

05. 거스름돈과 탐욕의 반례

  1. 25·10·5·1센트 동전으로 41센트를 큰 동전부터 거슬러 주는 과정을 쓰자.
  2. 25·10·1센트 동전만 있을 때 31센트에 대한 탐욕 결과와 최소 동전 수를 비교하자.
해설 보기
  1. 41→16→6→1→041\to16\to6\to1\to0으로 남는다. 동전은 25,10,5,125,10,5,1의 총 4개다.
  2. 탐욕은 25+1+1+1+1+1+125+1+1+1+1+1+1의 7개를 쓴다. 10+10+10+110+10+10+1이면 4개다. 3개 이하로는 만들 수 없다. 25를 쓰면 남은 6을 1센트 6개로 채워야 하고, 25를 안 쓰면 세 동전의 최대 합이 30이다. 따라서 최적은 4개다. 큰 동전부터 고르는 규칙이 모든 동전 구성에서 최적인 것은 아니다.

06. 일정 선택과 정지 문제

  1. 강연을 최대한 많이 선택할 때 “가장 짧은 강연부터” 고르면 항상 최적인가? 반례를 들자.
  2. 정지 문제가 풀 수 없다는 말의 뜻과 증명 아이디어를 설명하자.
해설 보기
  1. 아니다. A는 8:00–9:15, B는 9:00–10:00, C는 9:45–11:00이라고 하자. 가장 짧은 B를 고르면 A,C와 모두 겹쳐 1개만 고른다. 반면 A,C는 겹치지 않아 2개를 고를 수 있다.
  2. 임의의 프로그램과 입력의 정지 여부를 항상 정확히 판정하고 종료하는 알고리즘이 없다는 뜻이다. 그런 판정기 HH가 있다고 가정하고, H(P,P)H(P,P)가 정지한다고 하면 무한 반복하고 그렇지 않다고 하면 즉시 끝나는 프로그램 K(P)K(P)를 만든다. K(K)K(K)는 정지한다고 판정되면 멈추지 않고, 멈추지 않는다고 판정되면 멈춘다. 어느 경우든 모순이므로 HH는 존재할 수 없다. 특정 프로그램의 정지 여부를 전혀 판단할 수 없다는 뜻은 아니다.

07. 빅오 증인 찾기

양의 큰 xx에서 다음 빅오 관계를 보이는 C,kC,k를 하나씩 구하자.

  1. 5x3=O(x4)5x^3=O(x^4).
  2. 3x2+5x+2=O(x2)3x^2+5x+2=O(x^2).
  3. 7x4−3x2+6=O(x4)7x^4-3x^2+6=O(x^4).
해설 보기
  1. x>1x>1이면 5x3≤5x45x^3\le5x^4이므로 C=5,k=1C=5,k=1이다. C=1,k=5C=1,k=5도 된다.
  2. x>1x>1이면 5x≤5x25x\le5x^2, 2≤2x22\le2x^2이므로 전체가 10x210x^2 이하이다. C=10,k=1C=10,k=1.
  3. 절댓값의 삼각부등식과 x>1x>1을 사용하면
∣7x4−3x2+6∣≤7x4+3x2+6≤16x4.|7x^4-3x^2+6|\le7x^4+3x^2+6\le16x^4.

따라서 C=16,k=1C=16,k=1이다. 음의 계수가 있어도 절댓값을 다루면 안전하게 상한을 얻는다.

08. 지수함수는 이차함수의 빅오인가

2n2^n이 O(n2)O(n^2)인지 판단하자. n=10,20n=10,20에서 값을 비교한 뒤, 몇 개의 수치 확인을 넘어서는 근거를 제시하자.

해설 보기

n=10n=10이면 210=1024,n2=1002^{10}=1024,n^2=100, n=20n=20이면 220=1048576,n2=4002^{20}=1048576,n^2=400이다. 하지만 두 수치만으로 모든 상수 CC를 배제할 수는 없다.

rn=2n/n2r_n=2^n/n^2로 놓으면 n≥4n\ge4에서

rn+1rn=2(nn+1)2≥2(45)2=3225>1.\frac{r_{n+1}}{r_n}=2\left(\frac n{n+1}\right)^2 \ge2\left(\frac45\right)^2=\frac{32}{25}>1.

따라서 rn≥r4(32/25)n−4=(32/25)n−4r_n\ge r_4(32/25)^{n-4}=(32/25)^{n-4}로 한없이 커진다. 어떤 고정된 CC를 골라도 결국 2n>Cn22^n>Cn^2이므로 O(n2)O(n^2)가 아니다.

09. 합·곱과 증가율 비교

  1. 12+22+⋯+n21^2+2^2+\cdots+n^2의 빅오를 각 항의 상한으로 구하자.
  2. f1(x)=3x,f2(x)=5x2f_1(x)=3x,f_2(x)=5x^2일 때 f1+f2,f1f2f_1+f_2,f_1f_2의 빅오를 구하자.
  3. 다음을 증가율이 느린 순서로 나열하고 같은 세타인 것을 표시하자: (1.5)n(1.5)^n, 8n3+17n2+1118n^3+17n^2+111, (log⁡n)2(\log n)^2, 2n2^n, log⁡log⁡n\log\log n, n2(log⁡n)3n^2(\log n)^3, 2n(n2+1)2^n(n^2+1), n3+n(log⁡n)2n^3+n(\log n)^2, 1000010000, n!n!.
해설 보기
  1. 각 항이 n2n^2 이하이고 nn개이므로 합이 n3n^3 이하이다. 따라서 O(n3)O(n^3)다. 정확한 합 공식까지 쓰면 Θ(n3)\Theta(n^3)임도 알 수 있다.
  2. x>1x>1에서 3x+5x2≤8x23x+5x^2\le8x^2이므로 합은 O(x2)O(x^2), 곱은 15x315x^3이므로 O(x3)O(x^3)다.
  3. 다음은 충분히 큰 nn에서의 점근적 증가율 순서다.
10000 ≺ log⁡log⁡n ≺ (log⁡n)2 ≺ n2(log⁡n)3≺ {8n3+17n2+111, n3+n(log⁡n)2}≺ (1.5)n ≺ 2n ≺ 2n(n2+1) ≺ n!.\begin{gathered} 10000\ \prec\ \log\log n\ \prec\ (\log n)^2\ \prec\ n^2(\log n)^3\\ \prec\ \{8n^3+17n^2+111,\ n^3+n(\log n)^2\}\\ \prec\ (1.5)^n\ \prec\ 2^n\ \prec\ 2^n(n^2+1)\ \prec\ n!. \end{gathered}

중괄호 안 두 함수는 모두 Θ(n3)\Theta(n^3)이다. 로그의 고정 거듭제곱은 양의 거듭제곱 nεn^\varepsilon보다 느리고, 지수함수는 고정 차수 다항식보다 빠르다. ≺\prec는 여기서 앞 함수와 뒤 함수의 비가 0으로 간다는 뜻이며 모든 작은 nn에서의 수치 대소를 뜻하지 않는다.

10. 오메가와 세타의 증인

  1. 4x2+3x=Θ(x2)4x^2+3x=\Theta(x^2)를 상·하한 증인으로 보이자.
  2. x3=Ω(x3+2x+1)x^3=\Omega(x^3+2x+1)인가?
  3. O,Ω,ΘO,\Omega,\Theta가 각각 어떤 정보를 주는지 설명하자.
  4. f(x)=O(g(x))f(x)=O(g(x))의 등호가 보통 등식과 다른 이유는?
해설 보기
  1. x>1x>1에서 4x2≤4x2+3x≤7x24x^2\le4x^2+3x\le7x^2. 따라서 하한 상수 4, 상한 상수 7, 기준점 1을 고르면 된다.
  2. 그렇다. x>1x>1이면 x3+2x+1≤4x3x^3+2x+1\le4x^3이므로 x3≥14(x3+2x+1)x^3\ge\frac14(x^3+2x+1). 증인은 C=1/4,k=1C=1/4,k=1이다.
  3. OO는 상수배 상한, Ω\Omega는 상수배 하한, Θ\Theta는 둘을 동시에 준다. 최악/최선이라는 경우 구분 자체를 뜻하지 않는다.
  4. O(g)O(g)는 하나의 함수가 아니라 조건을 만족하는 함수들의 집합이다. f∈O(g)f\in O(g)가 집합론적으로 정확한 표현이며, f=O(g)f=O(g)는 관용적 표기다. 일반 등식처럼 양변을 자유롭게 교환해도 된다는 뜻이 아니다.

11. 혼합 함수의 차수와 기본 증가율

  1. 2x3+3x2log⁡2x+1002x^3+3x^2\log_2x+100의 빅오를 구하자.
  2. n2,nlog⁡n,2n,log⁡n,n!,1n^2,n\log n,2^n,\log n,n!,1을 증가율 순으로 나열하자.
해설 보기
  1. x>1x>1이면 log⁡2x≤x\log_2x\le x, 100≤100x3100\le100x^3이므로
2x3+3x2log⁡2x+100≤2x3+3x3+100x3=105x3.2x^3+3x^2\log_2x+100\le2x^3+3x^3+100x^3=105x^3.

따라서 O(x3)O(x^3)다. 또한 2x32x^3 이상이므로 Θ(x3)\Theta(x^3)까지 말할 수 있다. 2. 느린 순서로 1,log⁡n,nlog⁡n,n2,2n,n!1,\log n,n\log n,n^2,2^n,n!이다. 로그의 밑은 1보다 큰 고정 상수라고 가정한다.

12. 검색의 시간·공간과 평균 비교 횟수

  1. 시간 복잡도와 공간 복잡도의 차이는?
  2. 원소 10610^6개의 정렬된 배열에서 이진 검색의 최악 비교 횟수 상한을 구하자. 반복 조건과 원소 비교를 각각 세며, 종료 검사와 마지막 같은지 검사도 포함한다.
  3. 순차 검색은 x=aix=a_i이면 2i+12i+1회 비교한다고 하자. xx가 반드시 배열에 있고 각 위치의 확률이 1/n1/n이면 평균은?
  4. 순차·이진 검색의 최악 시간 복잡도는?
해설 보기
  1. 시간은 연산 횟수, 공간은 메모리 사용량을 입력 크기의 함수로 분석한다.
  2. 이 비교 기준에서 상한은 2⌈log⁡2n⌉+22\lceil\log_2n\rceil+2다. ⌈log⁡2106⌉=20\lceil\log_2 10^6\rceil=20이므로 42회다. 원소끼리의 비교만 세는 기준과 혼동하면 안 된다.
  3. 기대 비교 횟수는
1n∑i=1n(2i+1)=2⋅n(n+1)/2+nn=n+2.\frac1n\sum_{i=1}^n(2i+1) =\frac{2\cdot n(n+1)/2+n}{n}=n+2.

검색 실패의 확률을 포함하면 분포가 달라지므로 평균도 다시 계산해야 한다. 4. 순차 검색은 Θ(n)\Theta(n), 이진 검색은 Θ(log⁡n)\Theta(\log n)이다. 이진 검색은 정렬 조건을 전제한다.

13. 정렬의 비교 횟수

원소 10개에 대해 다음 비교 횟수를 구하자.

  1. 조기 종료 없이 매 회전의 끝을 하나씩 줄이는 버블 정렬.
  2. 삽입 위치를 앞에서부터 찾고 자기 자신과의 종료 비교까지 세는 삽입 정렬의 최악 원소 비교 수.

각 알고리즘의 최악 시간 복잡도도 쓰자.

해설 보기
  1. (10−1)+(10−2)+⋯+1=10⋅9/2=45(10-1)+(10-2)+\cdots+1=10\cdot9/2=45회다.
  2. jj번째 원소의 위치를 찾을 때 최대 jj회이므로 2+3+⋯+10=10⋅11/2−1=542+3+\cdots+10=10\cdot11/2-1=54회다. 이 버전은 이미 정렬된 입력에서 앞부터 끝까지 비교하므로 이 최대 비교 수가 나온다. 뒤에서 탐색하는 다른 삽입 정렬의 수치와 섞으면 안 된다.

두 방식 모두 최악 시간은 Θ(n2)\Theta(n^2)다. 비교 수에 원소 이동 비용까지 더해도 이 차수는 유지된다.

14. 행렬곱의 연산량과 괄호

  1. m×km\times k와 k×nk\times n 행렬을 정의대로 곱할 때 스칼라 곱셈은 몇 회인가?
  2. A1:10×100,A2:100×5,A3:5×50A_1:10\times100,A_2:100\times5,A_3:5\times50에서 (A1A2)A3(A_1A_2)A_3와 A1(A2A3)A_1(A_2A_3)의 곱셈 수를 비교하자.
  3. 두 n×nn\times n 행렬의 직접 곱셈 시간 복잡도와 다항 시간 여부를 설명하자.
해설 보기
  1. 결과 성분 mnmn개 각각에 kk번의 곱셈이 필요하므로 mknmkn회다.
  2. 왼쪽 괄호에서는 먼저 10×510\times5 행렬을 만들고, 오른쪽 괄호에서는 먼저 100×50100\times50 행렬을 만든다.
(A1A2)A3:10⋅100⋅5+10⋅5⋅50=7500,A1(A2A3):100⋅5⋅50+10⋅100⋅50=75000.\begin{aligned} (A_1A_2)A_3 &: 10\cdot100\cdot5+10\cdot5\cdot50=7500,\\ A_1(A_2A_3) &: 100\cdot5\cdot50+10\cdot100\cdot50=75000. \end{aligned}

왼쪽이 곱셈을 10분의 1만 사용한다. 행렬 순서는 그대로이며 괄호만 달라졌다. 3. 곱셈 n3n^3회다. 각 성분의 첫 곱을 초기값으로 두면 덧셈 n2(n−1)n^2(n-1)회, 0에 모든 곱을 누적하면 덧셈 n3n^3회다. 어느 쪽도 Θ(n3)\Theta(n^3)이며 산술 연산을 상수 비용으로 세는 모형에서 다항 시간이다. 계산 문제 자체를 엄밀한 결정 문제 클래스 P와 동일시하기보다는 다항 시간에 계산 가능하다고 표현한다.

15. 브루트포스와 최근접 점 쌍

  1. 브루트포스의 의미와 예 두 가지를 쓰자.
  2. 1,000개 점에서 모든 서로 다른 점 쌍을 한 번씩 비교하면 몇 쌍인가?
해설 보기
  1. 후보나 경우를 정의에 따라 직접 검사하는 접근이다. 예를 들어 순차 검색은 원소를 차례로 검사하고, 최근접 점 쌍의 브루트포스는 모든 점 쌍의 거리를 비교한다.
  2. 각 점에서 다른 점 999개를 고르면 1000⋅9991000\cdot999지만, (a,b)(a,b)와 (b,a)(b,a)를 중복 센다. 따라서 1000⋅999/2=4995001000\cdot999/2=499500쌍이다. 일반적으로 n(n−1)/2=Θ(n2)n(n-1)/2=\Theta(n^2)다.

16. 복잡도 정리와 NP-완전

  1. 순차 검색, 이진 검색, 기본 버블 정렬, 삽입 정렬, 직접 정사각행렬 곱셈의 최악 시간 복잡도를 쓰자.
  2. NP와 NP-완전의 관계 및 대표적인 NP-완전 문제를 설명하자.
해설 보기
  1. 차례로 Θ(n)\Theta(n), Θ(log⁡n)\Theta(\log n), Θ(n2)\Theta(n^2), Θ(n2)\Theta(n^2), Θ(n3)\Theta(n^3)다. 앞의 nn은 원소 수, 마지막 nn은 정사각행렬 한 변의 크기다.
  2. NP는 예라고 답할 입력에 대해 다항 길이의 증명서가 있고 이를 다항 시간에 검증할 수 있는 결정 문제들의 집합이다. NP-완전 문제는 NP에 속하면서 NP의 모든 문제가 다항 시간에 환원되는 문제다. 따라서 NP-완전 문제 하나를 다항 시간에 풀면 NP의 모든 문제도 다항 시간에 풀려 P=NPP=NP가 된다. SAT가 대표적이다. NP를 “다항 시간에 풀 수 없음”이라고 해석하면 안 된다.
Discussion

Comments