アルゴリズム実行時間計算

データ構造とアルゴリズム分析Java言語の説明から抜粋
2つのプログラムがほぼ同じ時間を費やすと考えられる場合、どのプログラムがより速いかを決定する最善の方法は、彼らを符号化して実行することである可能性が高い.
一般的に、集中アルゴリズム思想が存在するが、我々は常にそれらの悪いアルゴリズム思想をできるだけ早く除去したいので、通常、アルゴリズムを分析する必要がある.それだけでなく、分析を行う能力.それだけでなく、分析を行う能力は、計算優先アルゴリズムに対する動産能力を提供することが多い.一般的に、分析はボトルネックを正確に特定することができ、これらの場所は慎重に符号化する価値がある.
解析を簡略化するために,特定の時間単位は存在しないという約束を採用する.そこで,いくつかのプリアンブルの定数を捨て,低次項を捨てて,大きなO運転時間を計算する.大Oは上界であるため,プログラムの実行時間を過小評価しないように注意しなければならない.実際,解析の結果,プログラムが一定時間範囲で運転を終了できることが保障されている.プログラムは早めに終わるかもしれませんが、間違いはありません.
簡単な例:1^3+2^3+3^3+4^3+......+n^3+......

public static int sum(int n) {
    int partialSum;
    partialSum = 0;
    for (int i = 1; i <= n; i++) {
        partialSum += i *i * i;
    }
    return partialSum;
}

。 。partialSum = 0 return partialSum 。partialSum += i *i * i 4 （ ， ）， N 4N 。for i、 i<=N i 。 ， N+1 ， N ， 2N+2 。 ， 6N+4 。 O(N)。
プログラムを分析するたびにこれらの作業をすべて実証すると、このタスクはすぐに負担になります.我々は大きなOの結果を得たので,最終的な結果に影響を及ぼさない多くの近道が存在する.例えば、毎回実行されるpartialSum+=i*i*iの時間は明らかにO(1)に似ており、正確に計算すると2、3、または4などは愚かであり、これは重要ではないからである.int partialSumとforサイクルは明らかに重要ではないので、ここで通話料の時間は賢明ではありません.これは私たちにいくつかの法則を得させた.
法則1——forサイクル
1つのforループの実行時間は、forループ内の文の実行時間に反復の回数を乗じることが多い.
法則2——ネストされたforループ
これらのサイクルを内側から外側に分析します.ネストされたループのセット内の文の合計実行時間は、文の実行時間に、そのグループのすべてのforループのサイズの積を乗じます.例えば以下のプログラムセグメントはO(N^2)

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        System.out.println();

法則3——順序文
各文の実行時間を合計すればよい(これは、その最大値が得られた実行時間であることを意味する)例えば、次のプログラムセグメントは、コストO(N)を表示し、次にO(N^2)を使用するので、総量もO(N^2)であり、O(N)を無視する

for (int i = 1; i < n; i++) {
    System.out.println();
}
for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        System.out.println();

法則4-if/else文

if(condition)
    S1
else 
    S2

1つのif/else文の実行時間は、判断された実行時間を超えず、S 1およびS 2の実行時間の長さの合計の実行時間を加える.すなわち、実行時間は、判断された実行時間にS 1またはS 2の大きな実行時間を加えない.
…………
他の法則は瞑想であるが,分析の基本戦略は内部(または最も深い部分)から外へ仕事を展開させる.メソッド呼び出しがある場合は、まずこれらの呼び出しを分析します.再帰過程がある場合、再帰が実際に薄いベールで隠されたforサイクル(forサイクルに変換しやすい)にすぎない場合、分析は簡単である.次の再帰は実際にはforループです.

public static long factorial(int n) {
    if (n <= 1)
        return 1;
    else
        return n * factorial(n - 1);
}

これは特殊な例であるが,再帰が正常に使用されると,それを循環構造に変換することは困難である.この場合,解析は設計して繰返し関係を解く.

public static long fib(int n) {
    if (n <= 1)
        return 1;
    else
        return fib(n - 1) + fib(n - 2);
}

N 40 ， 。 T(N) fib(n) 。 N=0 N=1， ， ， T(0)=T(1)=1。 N 。 N>2， else ， else 。 fib(n-1), T(N-1) 。 fib(n) ：
T(N)=T(N-1)+T(N-2)+2 fib(N)=fib(N-1)+fib(N-2) T(N)>=fib(N) 。 fib(N)=fib(N-1)+fib(N-2) fib(N)>=(3/2)^N， T(N)>=(3/2)^N， 。
このプログラムが遅いのは、余分な仕事がたくさんあるからです.fib(n−1)+fib(n−2)文では、fib(n−1)呼び出し時に実際に1回fib(n−2)が計算されたが、この情報は破棄され、その後+の後に1回fib(n−2)が計算される.これらの捨てられた情報が再帰的に結合すると,大きな実行時間をもたらす.これは「何でも1回以上計算しない」最高の例かもしれませんが、再帰から離れて使用できないほど驚くべきではありません.