アルゴリズムの時間的複雑さについて述べる

問題1:アルゴリズムの優劣をどのように判断しますか?
答え:余分な空間オーバーヘッドを考慮しない場合は小さく,同じ問題に対して直感的に,この問題を解決するアルゴリズムに要する時間が少ないほど,このアルゴリズムの効率が高いと考えられる.
たとえば、秩序配列arrayで数keyを検索する必要がある場合は、このkeyの配列内の下付き文字を返します(このkeyは配列中に必ず存在すると仮定します).私たちの最初の反応は配列全体を巡ることです.

for(int i=0;i

暴力的に解くのは簡単だ
しかし、もし私たちのこの配列に1億個の数があれば、最悪の場合(例えば、この数字は配列の末尾にある)、私たちは完全な配列を遍歴してこの数を見つける必要があります.それでは、私たちが必要とする時間は非常に大きいので、このアルゴリズムはデータ量が大きい場合、そんなに友好的ではありません.
だから私たちは通常そうしないで、二分検索を使います.△検索範囲を半分に絞るたびに、この数が見つかるまで.

public static int rank(int [] array,int key)
{//  ：    
int low=0;
int height=array.length-1;
while(low<=height)
    {
    int mid=low+(height-low)/2 //       。
    if（keyarray[mid]) {low=mid+1;}
    else return mid;
    }


}

では、最悪の場合、この配列でこの数を探す必要があります.検索回数を計算してみましょう.第1回N/2、第2回N/2/2、第3回N/2/2
m回目のN/2^mが得やすいので、この数を見つける最悪の場合は(2^m=n、m=log 2(N))です.
long(2 N)のルックアップ回数はNよりはるかに小さい.だから統一の問題に対して、良いアルゴリズムと悪いアルゴリズムの効率は天と地の差がある.
 
アルゴリズムの動作の速さ(時間の長さ)がアルゴリズムの優劣を判断する一つであることを知っている以上(今日は時間の複雑さだけを話し,空間の複雑さも考慮しなければならない)、一般性、すなわちアルゴリズムの実行時間をどのように判断するか.
問題2:アルゴリズムが実行される時間を知る必要がある場合は、どうすればいいですか.
解決1:直接時間関数で統計すると、コンピュータによって時間が違いますが、時間を知りたいなら、毎回実際に操作しなければなりません.これは現実的ではありません.どのような方法で直感的にアルゴリズムの効率を得ることができますか.直感は問題の規模と関係があることを教えてくれた.
解決二,我々は直接数学モデルを用いて判断し,実行文の実行回数に基づいて,問題の規模である関数を導出した.この問題の規模は、最も頻繁に実行される文に依存します.アルゴリズムの実行時間は,最も頻繁な文を実行する時間に基づいて決定されることは明らかである.
 
例を挙げます.
Int count=0;
For(int i=0;i
     count++;
このアルゴリズム(一応アルゴリズムと呼ぶでしょう)、forループという文が実行される回数はNです.問題の規模もNである.
したがって,このアルゴリズムの実行時間はNに依存する.
 
例2:三数の和:

public static int sum(int [] a)
{       0       。
int count=0;
int N=a.length;
for(int i=0;i

このネストされた3層ループでは、If文が最も頻繁に実行される文であることがわかり、このアルゴリズムの実行回数として選択すると、その実行頻度はN(N−1)(N−2)/6=N^3/6−N^2/2+N/3となる.この式はここで導き出して、興味があれば自分で導き出すことができます.
近似を求める
しかし,このような解析によれば,文が実行する周波数をアルゴリズムの時間的複雑さとする.複雑な数学式が生成されると,このアルゴリズムの優劣を解析するのに不利である.例:
N(N-1)(N-2)/6=N^3/6-N^2/2+N/3.
この式は少し複雑に見えるかどうかは分かるが、一般的にこの式では、Nが大きくなるにつれて、第1項以降の他の項の値は相対的に小さい(例えば、N=1000の場合、N^2/2+N/3≒499 667、N^3/6≒166 666 667).これにより,我々の結果に及ぼす影響が小さいため,非常に複雑でべき乗の低い項を除去できることが分かった.
Nが増大し続けると,N^3/6−N^2/2+N/3をN 3/6で割った値は無限に1に近づく.近似値としてN^3/6を用いた
だから近似値N^3/6を取ります.
さらに係数を無視し,すべての注意力を問題規模に集中すると,このアルゴリズムの時間複雑度はN^3である.したがって,我々は後で時間複雑度をとる場合,最高次べき乗のみをとり,その係数を無視する.
 
 
関数＃カンスウ＃
近似
時間の複雑さ
N^3/6-N^2/2+N/3
N^3/6
N^3
N^2/2+N/3
N^2/2
N^2
lgN+1
lgN
lgN
3
3
1
 
よくある時間の複雑さのまとめ
説明
時間の複雑さ
標準コード
説明
定数レベル
1
a+b=c
一般文
対数レベル
logN
にぶんたんさく
二分策
線形レベル
N
For(int i=0;i { }
ループ
線形対数レベル
NLogN
ぶんかつ
集計ソート
平方レベル
N2
For(int i=0;i For(int j=i;j }
にじゅうサイクル
キューブ・レベル
N3
3つのforネストのforループ
さんそうサイクル
アルゴリズムの場合,時間的複雑さが低いほどよいことは明らかである.アルゴリズムの時間的複雑さが高すぎると、本当に遅いので、私たちには受け入れられません.
通常O(1)
参考:アルゴリズム第4版.