algorithm
アルゴリズムの複雑さ
サーチ…
備考
すべてのアルゴリズムは、問題を解決するためのステップのリストです。各ステップは、前のステップのいくつかのセット、またはアルゴリズムの開始に依存しています。小さな問題は次のようになります。
この構造は、有向非循環グラフ、つまりDAGと呼ばれています。グラフ内の各ノード間のリンクは、操作の順序による依存関係を表し、グラフにはサイクルが存在しません。
依存関係はどのように起こるのですか？たとえば、次のコードを考えてみましょう：
total = 0
for(i = 1; i < 10; i++)
total = total + i
このpsuedocodeでは、forループの各反復は、前回の反復で計算された値を使用しているため、前の反復の結果に依存します。このコードのDAGは次のようになります。
アルゴリズムのこの表現を理解すれば、それを使ってアルゴリズムと複雑さを作業とスパンの観点から理解することができます。
作業
仕事は、与えられた入力サイズnアルゴリズムの目標を達成するために実行される必要がある実際の操作の数です。
スパン
スパンはクリティカルパスと呼ばれることもあり、アルゴリズムの目的を達成するためにアルゴリズムが最低限必要とするステップ数です。
次の図は、グラフを強調表示し、サンプルDAGの作業とスパンの違いを示しています。
仕事はグラフ全体のノード数です。これは、上記の左のグラフで表されます。スパンはクリティカルパス、または開始から終了までの最長パスです。作業を並行して行うことができれば、右側の黄色い強調表示されたノードはスパンであり、必要なステップの数は最も少ない。作業を連続して行わなければならない場合、そのスパンは作業と同じです。
作業とスパンの両方を分析の観点から独立して評価することができます。アルゴリズムの速度はスパンによって決まります。必要とされる計算能力の量は、作業によって決定される。
ビッグ・シータ記法
Big-Thetaは、アルゴリズムの実行時間の上限のみを表すBig-O表記とは異なり、タイトな境界です。上限と下限の両方。タイト・バウンドはより正確ですが、計算が難しくなります。
Big-Theta記法は対称的である： f(x) = Ө(g(x)) <=> g(x) = Ө(f(x))
f(x) = Ө(g(x))とは、f（x）とg（x）のグラフが同じ速度で成長すること、またはグラフが同じように大きくなることを意味する十分なxの値。
Big-Theta表記法の完全な数式は次のとおりです。
n> nである場合に、c 1 <abs（g（n）/ f（n））である場合、Ψ（f（x））= {g：N 0 →Rおよびc 1 、c 2 、n 0 > 0かつabsは絶対値}
例
入力nアルゴリズムが42n^2 + 25n + 4演算を終了すると、それはO(n^2)だがO(n^3)とO(n^100) 。しかし、 Ө(n^2)あり、 Ө(n^3) 、 Ө(n^4)などではない。また、 Ө(f(n))あるアルゴリズムもO(f(n))その逆もありません！
形式的な数学的定義
Ө(g(x))は一連の関数である。
Ө(g(x)) = {f(x) such that there exist positive constants c1, c2, N such that 0 <= c1*g(x) <= f(x) <= c2*g(x) for all x > N}
ためӨ(g(x))セットであり、我々は書くことができるf(x) ∈ Ө(g(x))ことを示すために、 f(x)のメンバーであるӨ(g(x)) 。代わりに、私たちは通常、同じ概念を表現するためにf(x) = Ө(g(x))を書いていきます。これが一般的な方法です。
数式中にӨ(g(x))が出現するたびに、名前を付ける気にしない無名関数を表すものと解釈します。例えば、式T(n) = T(n/2) + Ө(n) 、意味T(n) = T(n/2) + f(n) f(n)セット内の関数であるӨ(n) 。
fとg実数のいくつかの部分集合に定義された2つの関数とする。我々は、書き込みf(x) = Ө(g(x))のようなx->infinityであれば、正の定数が存在する場合にのみ、 K及びLと実数x0保持するように：
K|g(x)| <= f(x) <= L|g(x)|すべてのx >= x0
定義は次のとおりです。
f(x) = O(g(x)) and f(x) = Ω(g(x))
限界を使う方法
もしlimit(x->infinity) f(x)/g(x) = c ∈ (0,∞)の限界が存在し、それは次いで、正のIE f(x) = Ө(g(x))
一般的な複雑さのクラス
| 名 | 記法 | n = 10 | n = 100 |
|---|---|---|---|
| 定数 | Ө（1） | 1 | 1 |
| 対数 | Ө（log（n）） | 3 | 7 |
| リニア | Ө（n） | 10 | 100 |
| 線形 | Ө（n * log（n）） | 30 | 700 |
| 二次 | Ө（n ^ 2） | 100 | 10000 |
| 指数関数的 | Ө（2 ^ n） | 1 024 | 1.267650e + 30 |
| 要因 | Ө（n！） | 3 628 800 | 9.332622e + 157 |
ビッグオメガ表記
漸化式の下限にはΩ-表記法が使用されます。
正式な定義
f(n)とg(n)正の実数の集合で定義される2つの関数とする。以下のような正の定数cとn0がある場合、 f(n) = Ω(g(n))と書く。
0 ≤ cg(n) ≤ f(n) for all n ≥ n0
ノート
f(n) = Ω(g(n))は、 f(n)がg(n)より漸近的に成長しないことを意味する。また、 Θ(g(n))または/およびO(g(n))に関する文でアルゴリズム分析が不十分である場合、 Ω(g(n))についても言える。
表記法の定義から定理に従う：
2ための任意の関数f(n)及びg(n)我々はf(n) = Ө(g(n))場合にのみf(n) = O(g(n)) and f(n) = Ω(g(n)) 。
図形的にΩ記法は、次のように表すことができる。
例えば、 f(n) = 3n^2 + 5n - 4することができます。次に、 f(n) = Ω(n^2) 。また、 f(n) = Ω(n) 、またはf(n) = Ω(1)であっても正しい。
完璧なマッチングアルゴリズムを解決するもう1つの例：頂点の数が奇数の場合、「完璧なマッチングなし」を出力し、そうでない場合はすべてのマッチングを試みます。
私たちはアルゴリズムが指数関数的な時間を必要としていると言いたいのですが、実際にはΩの通常の定義を使ってΩ(n^2)下限を証明することはできません。無限に多くのnに対して、ある一定のc>0 、 f(n)≥ cg(n)を言ってf(n)=Ω(g(n))定義するべきである。 f(n)=Ω(g(n)) iff f(n) != o(g(n)) 。
参考文献
正式な定義と定理は、 "Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。Introduction to Algorithms"の書籍から取られている。
漸近表記の比較
f(n)とg(n)正の実数の集合で定義される2つの関数とすると、 c, c1, c2, n0は正の実数定数です。
| 記法 | f（n）= O（g（n）） | f（n）=Ω（g（n）） | f（n）=Θ（g（n）） | f（n）= o（g（n）） | f（n）=ω（g（n）） |
|---|---|---|---|---|---|
| 正式な定義 | ∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) ≤ cg(n) | ∃ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) ≤ f(n) | ∃ c1, c2 > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ c1 g(n) ≤ f(n) ≤ c2 g(n) | ∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ f(n) < cg(n) | ∀ c > 0, ∃ n0 > 0 : ∀ n ≥ n0, 0 ≤ cg(n) < f(n) |
f, gと実数a, bの漸近比較 | a ≤ b | a ≥ b | a = b | a < b | a > b |
| 例 | 7n + 10 = O(n^2 + n - 9) | n^3 - 34 = Ω(10n^2 - 7n + 1) | 1/2 n^2 - 7n = Θ(n^2) | 5n^2 = o(n^3) | 7n^2 = ω(n) |
| グラフィック解釈 |  | |  |
漸近表記は、Venn図で次のように表すことができます。 
リンク
Thomas H. Cormen、Charles E. Leiserson、Ronald L. Rivest、Clifford Stein。アルゴリズムの紹介。