데이터 구조의 제2 장 알고리즘 분석 총화 및 방과 후 문제 답안

데이터 구조의 제1장 서론 및 방과 후 문제 답안
본 장 은 주로 절차 시간의 복잡 도 에 대한 계산 분석 방법 을 배 웠 다. 이 목적 을 바탕 으로 수학 기초, 모델 등 지식 점 을 파악 해 야 하기 때문에 본 장의 과정 구 조 는 다음 과 같다.

수학 기초

모델

분석 해 야 할 문제

운행 시간 계산 아래 하나씩 정리 분석 을 한다.수학 기 초 는 네 가지 정 의 를 기억 해 야 한다.

 - T(N) = O(f(N))     ，T(N)          f(N).  N=O(N^2)
 - T(N) = Ω（f(N)）    ，T(N)          f(N).  N^2=Ω(f(N))
 - T(N) = Θ(f(N))    ，T(N)        f(N)    ，  N = Θ(2N)
 - T(N) = o(f(N))     ，T(N)        f(N),     . 
       ，       。  ，         ：
 - T1(N)=O(f(N))   T2(N)=O(g(N)),  ：
   T1(N)+T2(N) = max(O(f(N)), O(g(N)))
   T1(N)*T2(N) = O(f(N)*g(N))
   exp:
   N=O(N^2) N^3=O(N^4) ==> N+N^3=max(O(N^2), O(N^4))=O(N^4).
   N=O(N^2) N^3=O(N^4) ==> N*N^3=O(N^2*N^4)=O(N^6)
 - T(N)   k    ， T(N)=Θ(N^k). 
   exp:
   1+N^2+N^3 = Θ(N^3).          N^3        。
 -           ，     。

모형.
대략.
분석 할 문제
1. 최대 하위 서열 과 A1, A2, A3,...................................................................하위 서열 이란 이 N 개 수의 연속 적 인 하위 항목 으로 구 성 된 집합 을 말한다.예 를 들 어 (A1, A2), (A2, A3, A4), (A1, A2, A3) 등 이지 만 (A1, A3) 은 본 고의 하위 서열 개념 에 속 하지 않 는 다. 왜냐하면 아래 표 지 는 연속 적 이지 않 기 때문이다.책 에 서 는 네 가지 해결 방안 을 제시 하 였 으 며, 다음은 하나씩 분석 하 였 다.

모든 연속 적 인 하위 서열 을 구하 고 각 서열 의 합 을 하나씩 구 한 다음 에 가장 큰 것 을 취한 다.

#include 
#include 
using namespace std;
int maxSubSum1( const vector<int> &a )  
{   
    int maxSum = 0;  
    for(int i=0; i//i            
    {   
        for(int j=i; j//j            
        {   
            int thisSum =0;  
            for( int k=i; k<=j; k++ )  //            ，               
            {   
                thisSum += a[k];  
                cout<" "<cout<if(thisSum>maxSum)  
{   
maxSum = thisSum;  
}  
}  
}  
return maxSum;  
}

이 방법 은 비교적 직관 적 이어서 코드 중의 주석 을 보고 계수기 의 의 미 를 이해 하면 매우 간단 하 다.그러나 이 방법 은 세 번 순환 되 고 복잡 도 는 O (N ^ 3) 이다.일반적인 복잡 도 법칙 은 다음 과 같다.

  for       O(N)
  for    O(N^k)
                。          ？

복잡 도 낮 추기 O (N ^ 2) 의 실현

int maxSubSum2(const vector<int> &a)
{
    int maxSum = 0;
    for (int i=0;iint thisSum=0;
        for (int j=i; jif (thisSum>maxSum)
            {
                maxSum = thisSum;
            }
        }
    }
}

사실 왜 그런 지 모 르 겠 어 요. - 선형 복잡 도.

int maxSubSum3(const vector<int> &a, int left, int right)
{
    int maxSum = 0;int thisSum=0;
    for (int i=left;iif (thisSum>maxSum)
        {
            maxSum = thisSum;
        }else if(thisSum<0)
        {
            thisSum = 0;
        }
    }
    return maxSum;
}

하 긴 못 알 아 보 겠 으 니 기억 해라.
방과 후 답안