《알고리즘 도론》 제4장 분할 치료 전략 개인 노트

제4장 분치 전략

이 장은 두 가지 예를 통해 분치 전략을 소개한 다음에 세 가지 방법으로 귀속식을 구한다.

4.1 최대 하위 그룹 문제

FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
left_sum = - MAX
sum = 0
for i = mid downto low
    sum = sum + A[i]
    if sum > left_sum
        left_sum = sum
        max_left = i
right_sum = - MAX
sum = 0
for j = mid + 1 to high
    sum = sum + A[j]
    if sum > right_sum
        right_sum = sum
        max_right = j
return(max_left, max_right, left_sum + right_sum)

FIND-MAXIMUN-SUBARRAY(A, low, high)
if high == low
    return(low, high, A[low])
else
    mid = (low + high) / 2
    (left_low, left_high, left_sum) = FIND-MAXIMUN-SUBARRAY(A, low, mid)
    (rihgt_low, rihgt_high, rihgt_sum) = FIND-MAXIMUN-SUBARRAY(A, mid + 1, high)
    (cross_low, cross_high, cross_sum) = FIND-MAX-CROSSING-SUBARRAY(A, low, mid, high)
    if left_sum >= right_sum and left_sum >= cross_sum
        return(left_low, left_high, left_sum)
    elseif right_sum >= left_sum and right_sum >= cross_sum
        return(right_low, right_high, right_sum)
    else
        return(cross_low, cross_high, cross_sum)

여기에는 분치 전략을 보여주기 때문에 이렇게 하지만 복잡도가 약간 높다. T(n)=Θ(nlgn) . 여기서 내가 비교적 간단하다고 생각하는 방법을 제시하는데 그 본질은 동적 기획이다.

FIND-MAXIMUN-SUBARRAY(A, low, high)
now_sum = -MAX
max_sum = -MAX
left = low
right = low
for i = low to high
    if now_sum < 0
        now_sum = 0
        left = i
    now_sum +=A[i]
    if now_sum > max_sum
        max_sum = now_sum
        right = i
return(left, right, max_sum)

4.2 행렬 곱셈의Strassen 알고리즘

일반 방법: T(n)=Θ(n3)

SQUARE-MATRIX-MULTIPLY(A, B)
n = A.row
let C be a new nxn matrix
for i = 1 to n
    for j = 1 to n
        C[ij] = 0
        for k = 1 to n
            C[ij] += A[ik] * B[kj]

Strassen 메서드: T(n)=Θ(nlg7) 1. A, B, C를 n2로 분해×n2의 하위 행렬 2.n2 10개 만들기×n2의 행렬 S1, S2,...,S10, 각 매트릭스 저장 단계 1에서 생성된 두 하위 매트릭스의 합계나 차이 3.단계 1에서 생성된 하위 매트릭스와 단계 2에서 생성된 10개의 매트릭스로 7개의 매트릭스 적 P1, P2,...,P7 4. Pi 행렬의 서로 다른 조합을 통해 가감 연산을 진행하여 결과 행렬 C의 하위 행렬 C11, C12, C21, C22를 계산한다
2단계에서 다음 10개의 행렬을 생성합니다.
S1=B12−B22S2=A11+A12S3=A21+A22S4=B21−B11S5=A11+A22S6=B11+B22S7=A12−A22S8=B21+B22S9=A11−A21S10=B11+B12
3단계에서 행렬 곱셈 7번을 반복적으로 계산합니다.
P1=A11S1P2=S2B22P3=S3B11P4=A22S4P5=S5S6P6=S7S8P7=S9S10
4단계, C의 하위 행렬을 얻기:
C11=P5+P4−P2+P6C12=P1+P2C21=P3+P4C22=P5+P1−P3−P7
주: 어차피 나는 이 행렬 계산을 기억할 수 없고, 기억하고 싶지도 않다. Strassen 방법은 그다지 실용적이지 않다.지금까지 nxn 행렬이 곱한 점진적인 복잡도가 가장 좋은 알고리즘은 Coppersmith와 Winograd가 제시한 것으로 운행 시간은 O(n2.376)로 이미 매우 좋다. 왜냐하면 하계는 Ω(n2)이기 때문이다.

4.3 대입법으로 귀속식 구하기

단계:

추측해의 형식

수학 귀납법으로 해중 상수를 구하고 해석이 정확하다는 것을 증명한다

4.4 귀속 트리로 귀속식 구하기

2.2절에서 귀속 트리를 사용했으니 2.2절의 내용을 참고할 수 있다.귀속수는 주로 각 층의 대가와 귀속수의 층수를 계산한다.

4.5 주 방법으로 귀속식 구하기

정리 4.1(주정리): a≥1과 b>1은 상수이고 f(n)는 함수이며 T(n)는 비음정수에 정의된 귀속식이다.
T(n)=aT(n/b)+f(n)
그렇다면
T(n)는 다음과 같습니다.
1. 어떤 상수에 대해
ε>있다
f(n)=O(nloga−εb),
T(n)=Θ(nlogab)
2. 만약에
f(n)=Θ(nlogab),
T(n)=Θ(nlogablgn)
3. 어떤 상수에 대해
ε>있다
f(n)=Ω(nloga+εb), 그리고 상수
c<1과 모든 충분한 n은
af(n/b)≤cf(n),
T(n)=Θ(f(n))
주: 여기의 작은 크기는 모두 다항식의 의미에서 큰 것보다 작은 것을 가리킨다. 만약에 함수 f(n)가 간극에 떨어지면 주된 방법으로 귀속식을 구할 수 없다.