アルゴリズムの漸近表現法と分析

アルゴリズム#アルゴリズム#

問題を段階的に解決するステップ

正確性:指定された入力に対して、正しい年は

でなければならない.

実行性:アルゴリズムの各ステップはコンピュータ上で実行する必要があります.

有限性:一定時間以内に結果を出す必要がある

効率(パフォーマンス):時間および空間効率

として定義する必要があります.

アルゴリズムの漸近表現

十分な大きさの記号を入力

Big-O(Bigo)

Big-Θ(大栓塔)

メガΩ

Big-O

漸近上限を表す.
これは、実行時間がどんなに遅くても、対応する上限時間を超えないことを意味します.


Big-Ω
Big‐Oとは対照的に,これは漸近下限を意味する.
これは、実行時間がどんなに速くても、対応する下限時間よりも速くないことを意味します.

Big-Θ
Big‐OとBig‐Ωの交差の概念.
実行時間はBig−OとBigΩの間にあることを意味する.

点火式の漸近分析方法

反復置換:より小さな問題の関数を使用して

反復置換

推定後証明:結論を推定し、数学的帰納法を用いて証明する方法

プライマリ・データのまとめ:

フォーマットに適合する点火式の複雑さを示します.
繰り返し置換
例1)

int factorial(int n)
{
    if(n == 1) return 1;
    return n * factorial(n-1);
}

階乗関数nで!命を救うのに要する時間
T(n)なら、
T(n)=T(n−1)+c=T(n−1)+c=T(n−2)+c+c=T(n−2)+2c=T(n−3)+3c=...=T(1)+(n−1)c T(1)≤cT(1)+(n−1)c≤c+(n−1)c=cnT(n) = T(n-1) + c\\= T(n-1) + c = T(n-2) + c + c = T(n-2) + 2c\\= T(n-3) + 3c\\= ...\\= T(1) + (n-1)c\\\\\T(1) ≤ c\\T(1) + (n-1)c ≤ c + (n-1)c = cnT(n)=T(n−1)+c=T(n−1)+c=T(n−2)+c+c=T(n−2)+2c=T(n−3)+3c=...=T(1)+(n−1)c T(1)≤cT(1)+(n−1)c≤c+(n−1)c=cn
上記のBig−OからT(n)＝O(n)であることが分かる.
例2)
T(n) = T(n-1) + n
与えられたT(1)=1の場合、
T(n)=T(n−1)+n=(T(n−2)−(n−1))+n=(T(n−3)−n−2)−(n−1)+n=....=T(n−(n−1))−n−(n−2)+n−(n−3)+...+(n−2)+(n−1)+n=1+2+3+...+n=n(n+1)/2=(1/2)n2+(1/2)=Θ(n2)T(n) = T(n-1) + n\\= (T(n-2) - (n-1)) + n\\= (T(n-3) - n-2) - (n-1) + n\\= ....\\= T(n-(n-1)) - n-(n-2) + n-(n-3) +... + (n-2) +(n-1) + n\\= 1 + 2 + 3 + ... + n\\= n(n+1)/2 = (1/2)n^2 + (1/2)\\= Θ(n^2)T(n)=T(n−1)+n=(T(n−2)−(n−1))+n=(T(n−3)−n−2)−(n−1)+n=....=T(n−(n−1))−n−(n−2)+n−(n−3)+...+(n−2)+(n−1)+n=1+2+3+...+n=n(n+1)/2=(1/2)n2+(1/2)=Θ(n2)
(例1に示すように、T(1)≦cはT(1)=1ではない.)
例3)
T(n) = 2T(n/2) + n
与えられたT(1)=1の場合、
T(n)=2T(n/2)+n=2(2T(n/22)+n/2)+n =22T(n/22)+2n =...=2k2T(n/2k)+knT(n) = 2T(n/2) + n\\= 2(2T(n/2^2) +n/2) + n\\\\\= 2^2T(n/2^2) + 2n\\\\\= ... = 2^k2T(n/2^k) + knT(n)=2T(n/2)+n=2(2T(n/22)+n/2)+n =22T(n/22)+2n =...=2k2T(n/2k)+kn
こちらです.
k=log2nk = log2nk=log2n
仮に.
では.
n=2kn = 2^kn=2k
そして.
nT(n/n)+nlogn=n+nlogn =Θ(nlogn)nT(n/n)+nlogn\\=n + nlogn\\\\\=Θ(nlogn)nT(n/n)+nlogn=n+nlogn =Θ(nlogn)
を選択します.
でもk=log2nと仮定しても大丈夫ですか?
この点の実行可能性を証明してください.

T(n)≦T(2 k)≦T(2 n)におけるT(n)=T(2 n)である.
T(n) = T (2k) = T(2n)
したがって,k=log 2 nと仮定しても漸近複雑度は同じである.
推定後証明
T(n)=2 T(n/2)+nの場合
すいてい
T(n)=O(nlogn)=>T(n/2)=O((n/2)log(n/2))T(n)=O(nlogn)\\=> T(n/2) = O((n/2)log(n/2))T(n)=O(nlogn)=>T(n/2)=O((n/2)log(n/2))
そう推測しましょう.
2T(n/2)+n=2c(n/2)log(n/2)+n=cnlogn−cnlog2+n=cnlogn+(1−clog2)n ≤cnlogn2T(n/2)+n\\=2c(n/2) log(n/2) + n\\=cnlogn -cnlog2 + n\\=cnlogn +(1-clog2)n\\\\\≤ cn log n2T(n/2)+n=2c(n/2)log(n/2)+n=cnlogn−cnlog2+n=cnlogn+(1−clog2)n ≤cnlogn
これらの不等号を満たすc
1−clog2≤01≤c1-clog2≤0\\1≤c1−clog2≤01≤c
そのため推定の仕方を証明することができる.
マスターファイルの整理
T(n)=aT(n/b)+f(n)等の形状の点火式
主の定理によって結果がわかる.

仮にそうであれば、
f(n)、h(n)を比較する場合
1.h(n)より大きい->h(n)実行時間の決定
2.f(n)より大きい->f(n)実行時間の決定
3.h(n)=f(n)->実行時間:h(n)*logn