알고리즘 도론 학습 노트 (3) 초고

몇 가지 소개념

하위 문제가 귀속구해를 사용할 정도로 충분할 때 귀속상황

이라고 한다.

하위 문제가 귀환할 필요가 없을 정도로 충분할 때 기본 상황

이라고 한다.

등식이나 부등식은 모두 귀속식

이라고 할 수 있다.

귀속을 구하는 세 가지 방법: 대입법, 귀속수법, 주방법

등식 귀속에 대한 결과는 다음과 같다.Θ,부등식은 Ω 또는Ο

분치할 때 두 부분의 위에서 아래로 정돈, 귀속식의 경계 조건 등 세부 사항은 무시할 수 있다

4.1 인용 예--최대 하위 그룹

폭력 구해법

모두 정수: 두 층의 순환이 최대 차이를 구하는 경우

유정유음: 먼저 전정으로 바꾸고 두 층이 순환하여 최대 차치를 구한다

분치법

두 가지 상황

모두 정수: 양과 음의 간략화 형식(인접상감)

플러스 마이너스: 단순화 필요 없음

구해사상-수조를 세 부분으로 나눈다. 완전히 중간에서 왼쪽으로, 완전히 중간에서 오른쪽으로, 좌우를 관통한다

세부 코드

#include <iostream>
#include <algorithm>
using namespace std;

struct qu{
    int left;
    int right;
    int result;
    qu()
    {
        left=right=0;
        result=0;
    }
    qu(int le, int ri)
    {
        left=le;
        right=ri;
    }

    qu& operator =(const qu& temp)
    {
        left=temp.left;
        right=temp.right;
        result=temp.result;
        return *this;
    }

};
qu maxcross(int *a, int l, int m, int r)
{
    int i,j;
    int maxi=a[m], maxj=a[m+1];
    int resulti=m,resultj=m+1;
    int temp1=maxi,temp2=maxj;

    for(i=m-1; i>=l; i--){
        temp1+=a[i];
        if(temp1>maxi){
            maxi=temp1;
            resulti=i;
        }
    }
    for(j=m+2; j<=r; j++){
        temp2+=a[j];
        if(temp2>maxj){
            maxj=temp2;
            resultj=j;
        }
    }

    qu Q(resulti,resultj);
    Q.result=maxi+maxj;
    return Q;
}

qu maxsub(int *a, int l, int r)
{
    if(l>=r){
        qu temp(l,l);
        temp.result=a[l];
        return temp;
    }
    int m=(l+r)/2;
    qu Q[3];
    Q[0]=maxsub(a,l,m);
    Q[1]=maxsub(a,m+1,r);
    Q[2]=maxcross(a,l,m,r);

    qu maxq;
    maxq=Q[0];
    if(Q[1].result>maxq.result)
        maxq=Q[1];
    if(Q[2].result>maxq.result)
        maxq=Q[2];
    return maxq;
} 

int main(){
    int a[16]={13,-3,-25,20,-3,-16,-23,18,20,
    -7,12,-5,-22,15,-4,7};
    qu re;

    re=maxsub(a,0,15);
    cout<<re.left<<" "<<re.right<<endl;
    cout<<re.result<<endl;
    return 0;
}

4.2 행렬 곱셈

일반 알고리즘(Θ(n^3^))

일반 분할

귀속분할(하표로 분할)

Strassen 메서드

단계 개요:

분해 매트릭스: 아래 표기 계산법으로 n/2*n/2의 하위 매트릭스

로 분해

S1 생성,...,S10 n/2*n/2 하위 매트릭스 10개 및 값 부여

7개 행렬의 적P1을 귀속적으로 계산,P7

Pi의 다른 조합을 통한 계산 결과

매트릭스 S
S1=B12−B22
S2=A11+A12
S3=A21+A22
S4=B21−B11
S5=A11+A22
S6=B11+B22
S7=A12−A22
S8=B21+B22
S9=A11−A21
S10=B11+B12

곱하기
P1=A11⋅S1
P2=S2⋅B22
P3=S3⋅B11
P4=A22⋅S4
P5=S5⋅S6
P6=S7⋅S8
P7=S9⋅S10

마지막 가감법 연산

C11=P5+P4−P2+P6
C12=P1+P2
C21=P3+P4
C22=P5+P1−P3−P7

4.3 소박한 대입법(수학 귀납법)

수학 귀납법의 기본 지식을 운용하는 동시에 점진 기호가 생략한 비교적 작은 항목을 고려한다.

4.4 본질의 귀속수법(구조 분석)

주요 목적은 좋은 추측을 생성하는 것이기 때문에 통상적으로 매우 정확하지 않다
다음을 포함합니다.

반올림 무시

노드의 결함을 무시하고 전체 트리로 가정

4.5 이성적인 주법(성질 사용)

내용

T(n)=aT(n/b)+f(n)의 추이식

어떤 상수가 존재한다면ε>0, f (n) = O (nlogba:ϵ) ,그러면 T(n) =Θ(nlogba)

f(n)=Θ(nlogba), T(n)=Θ(nlogbalgn)

어떤 상수가 존재한다면ε>0, f(n) = Ω(nlogb)

f(n)=Θ(nlogba lgkn), 그럼 T(n)=Θ(nlogba lgk+1n)

결함 - f(n)는 nlogba와 n이 있어야 한다ϵ 간극

결함 예 T(n) = 2T(n/2) + nlgn