データ構造とアルゴリズム----緒論

アルゴリズムの性質

貧乏性

能行性

確定性

終止性

-入出力
アルゴリズムの説明

自然言語記述

自然言語プラス数学式

プログラミング言語記述

-疑似コード記述
ノーマルデザインモード

列挙法は,具体的な問題に基づいて様々な可能性を挙げ,そこから有用な情報や問題の解を選択する.この方法はコンピュータの速度の優位性を利用して,問題を解決する際に非常に有効である.

問題の情報に基づいてできるだけ部分的な解をし,部分的な解に基づいて徐々に拡張して完全な解を得ることに貪欲である.複雑な問題を解決する時、このようなやり方は必ずしも最良の解を得ることができるとは限らない.

分治法は複雑な問題を比較的簡単なサブ問題に分解し,それぞれ解き,最後にサブ問題の解を組み合わせることで原問題の解を得た.

遡及法(探索法)は探索によって解くことを指す.問題が複雑で、明確な解法がない場合は、ステップ別に行う必要があり、各ステップには複数の選択肢がある可能性があります.この場合,探り方しか採用できず,実際の状況に応じて可能な方向を選択し,後の解の方向が継続できない場合には,前のステップに戻り,また解の経路を選択する必要があり,この動作は遡及となる.

動的計画法は、いくつかの複雑な状況下では、問題の解を直接行うことが困難であるため、前のステップで情報を蓄積し、後続のステップで既知の情報に基づいて既知の最良の解法経路を動的に選択する必要がある(同時に、情報をさらに蓄積する可能性がある).

分岐限界法

検索方法の改良形式と見なすことができ、検索過程でいくつかの情報を得ることができ、いくつかの可能な選択が実際に本当に役に立たないことを確定すれば、早期に削除して、解の空間を縮小し、問題の解の過程を加速することができる.
えんざんじかんけいさん
一般法則
法則1-forループ
1つのforループの実行時間は、forループ内の文の実行時間に反復を乗じた回数が多い.
法則2-ネストされたforループ
これらのサイクルを内側から外側に分析します.ネストされたループのセット内のいくつかの文の合計実行時間は、文の実行時間に、そのグループのすべてのforループのサイズの積を乗じます.たとえば、次のプログラム断片はO(n 2)です.

for(i = 0;i < n; i++){
    for(j = 0;j < n; j++){
        k++;
    }
}

法則3-順序文
各文の実行を実際に合計すればよい.nとn 2をn 2に加算
法則4-if/else文

if(condition) s1
else s2

1つのif/else文の実行時間は、判断された実行時間を超えず、s 1およびs 2の実行時間長者の合計実行時間を加えたものである.
分析の基本戦略は内部から外部に展開される.メソッド呼び出しがある場合は、まずこれらの呼び出しを分析します.
最大サブシーケンスと問題

//            
//            
//                      
//   ：n^3
public static int maxSubSum1(int[] a){
    int maxSum = 0;
    for(int i = 0; i < a.length; i++){

        for (int j = i; j < a.length; j++){

            int thisSum = 0;

            for(int k = i; k <= j; k++) thisSum += a[k];
            if (thisSum > maxSum) maxSum = thisSum;

        }

    }
    return maxSum;
}

//            
//            
//1,2       ：
// 1.  1                 
// 2.  2            ，          ，              
//   ：n^2
public static int maxSubSum2(int[] a){

    int maxSum = 0;

    for(int i = 0; i < a.length; i++){

        int thisSum = 0;
        for (int j = i; j < a.length; j++){


             thisSum += a[j];
            if (thisSum > maxSum) maxSum = thisSum;

        }

    }
    return maxSum;
}

//        nlogn
private static int maxSumRec(int[] a, int left, int right){

    if (left == right){
        if (a[left] > 0) return a[left];
        else return 0;
    }

    int center = (left + right) / 2;

    int maxLeftSum = maxSumRec(a, left, center);
    int maxRightSum = maxSumRec(a, center + 1, right);

    int maxLeftBorderSum = 0, leftBorderSum = 0;
    for (int i = center; i>=left; i--){
        leftBorderSum += a[i];
        if (leftBorderSum > maxLeftBorderSum) maxLeftBorderSum = leftBorderSum;
    }
    int maxRightBorderSum = 0, rightBorderSum = 0;
    for (int i = center + 1; i <= right; i++){
        rightBorderSum += a[i];
        if (rightBorderSum > maxRightBorderSum) maxRightBorderSum = rightBorderSum;
    }
    System.out.println(maxLeftBorderSum+","+maxRightBorderSum);
    return max3(maxLeftBorderSum,maxRightBorderSum,maxLeftBorderSum+maxRightBorderSum);
}
private static int max3(int num1, int num2, int num3){
    int max = num1 > num2 ? num1 : num2;
    max = max >num3 ? max :num3;
    return max;
}
//1,2     ，                  
public static int maxSubSum4(int[] a){
    int maxSum = 0,thisSum = 0;
    for(int j = 0; j < a.length; j++){
        thisSum += a[j];
        if (thisSum > maxSum){
            maxSum = thisSum;
        }
        else if(thisSum < 0){
            thisSum = 0;
        }
    }
    return maxSum;
}