【アルゴリズム設計と分析】第1章序論

第1章序論

関連紹介

アルゴリズムの正確性

アルゴリズムの複雑性

時間複雑性

時間複雑度記号

1、上有界O

、下に界Ω\OmegaΩ

があります.

多項式複雑度

指数の複雑度

、同階θ\テータθ

演算規則

空間複雑性

紹介について
(アルゴリズム＋データ構造)=プログラム
図霊——コンピュータ科学の父、人工知能の父の図霊賞——コンピュータ界のノーベル賞の図霊テスト
アルゴリズムの関連性:入出力、確定性、有限性
アルゴリズム:問題を解決する方法またはプロセス
アルゴリズムの正確性
一つのアルゴリズムが正しい場合、各入力が最終的に停止され、正しい出力が生成される.
プログラムのデバッグはプログラムの間違いを証明するだけで、プログラムに間違いがないことを証明することができません.
アルゴリズムの複雑性
時間の複雑さ
一つのアルゴリズムは抽象的なコンピュータ上で動作するために必要な時間(特定の入力に対して結果を生成するために必要な原子動作または「ステップ」数)T=T(N,I)T=T(N,I)T=T=T=T(N,I)
N:問題の規模I:入力
1、最悪の場合の時間複雑性2、最良の場合の時間複雑性3、平均的な場合の時間複雑性
時間複雑記号
f(N)とg(N)は、正の数セットに定義された正の関数であり、正常数C Cと自然数N 0 N_があれば、0 N 0
1、上有界O O
f(N)f(N)f(N)Nが十分大きいと、上に境界がある:N≧N 0 N\geq N_0 N≧N 0の場合、f(N)≦C g(N)f(N)\leq Cg(N)f(N)≦Cg(N)、g(N)g(N)g(N)g(N)f(N)f(N)の一つの上界があります. f(N)=O(g(N))O(1)O 2)<
2、下界Ω\OmegaΩがあります.
f(N)f(N)f(N)Nが十分大きい場合、境界があります.N≧N 0 N\geq N_0 N≧N 0の場合、f(N)≧C g(N)f(N)\geq Cg(N)f(N)≧Cg(N)、g(N)g(N)g(N)g(N)g(N)g)g(N)f(N)f)f(N)N)f)f(N)N)N)N)f(N)N)f(N)N)f)f(N)f)f(N)の境界)f)f f(N)=Ω(g(N))多項式複雑度
高い効率の計算方法、ハードウエアを積み重ねます.
指数の複雑さ
非効率アルゴリズムは、ハードウェアのスタックは不要です.
3、同階θ\テータθ
f(N)f(N)f(N)f(N)は、g(N)g(N)g(N)g(N)と同次である場合、f(N)＝O(g(N))f(N)＝O(N)f(g(N)＝O(g(N))、f(N)＝Ω(g(N))f(N)f(N)＝Omega(N)(f) f(N)=θ(g(N))演算規則

O(f) + O(g) = O(max(f,g))
O(f) + O(g) = O(f + g)
O(f)O(g) = O(fg)
 g(N) = O(f(N))， O(f) + O(g) = O(f)
O(Cf(N)) = O(f(N))，  C       
f = O(f)

スペース複雑性
1つのアルゴリズムは、特定の入力に対して結果を生成するために必要な記憶空間サイズS＝S(N,I)S＝S(N,I)S＝S(N,I)を格納する.