さまざまなアルゴリズムのビッグシータ境界を見つける方法を学ぼうとしていますが、ここでいくつかの質問を読んだり、講義や教科書を読んだりしても、その方法を理解するのに苦労しています。たとえば
procedure for array a{
step=1
while(step <= n){
i = n
while(i >= step){
a[i]= a[i-step] + a[i]
i = i - 1}
step = step * 2}
}
配列 a のインデックスの数 n に関して、これが通過する追加の数のビッグシータ境界を把握したいと思います。外側のループ自体が log(n) 回繰り返されることはわかりますが、内側のループで何が起こっているかを表現する方法がわかりません。誰かが説明を持っていますか、あるいは私が相談できるリソースさえありますか?
Big Theta表記では、十分に大きな n に対して関数 f(n) が k1*g(n) と k2*g(n) の間にあるような 2 つの定数 k1 と k2 を見つけるよう求められます。言い換えれば、ある点で f(n) よりも小さく、別の点で f(n) よりも大きい他の関数 g(n) を見つけることができますか (それぞれ単調に)。
Big-Theta を証明するには、f(n) が O(g(n)) (上限)、f(n) が Big-Omega(g(n)) (下限) となるような g(n) を見つける必要があります。バウンド）。
Big-O表記 (f(n) <= g(n)*k) に関しては、アルゴリズム f(n) は O(log(n)*n) です。この場合、g(n) =ログ (n) * n。
これを証明しましょう:
外側のループは何回実行されますか? 「ステップ」変数を追跡します: n が 100 であるとしましょう:
これは、100 の入力に対して 7 回の実行です。同等に、それは何回も実行されると言え(log n)ます (実際には floor(log n) 回ですが、log(n) で十分です)。
次に、内側のループを見てみましょう。i 変数を追跡します。この変数は、反復ごとnにそのサイズになるまで減少します。したがって、内側の while ループは、step の値ごとに n - step 回実行されます。step
たとえば、n = 100
では、内側のループの合計反復回数は?
このことはどのように成長していますか？外側のループが log(n) 回反復することがわかっているので、これを総和として定式化できます。
Sum(i=0 から log(n) まで) n-2^i
= log(n)*n - Sum(i=0 から log(n) まで) 2^i
= ログ(n)*n - (2^0 + 2^1 + 2^2 + ... + 2^ログ(n))
= log(n)*n - ( (1-2^log(n) ) / (1-2) ) (実際には 2^log(n+1) ですが、十分に近い)
= ログ (n) * n + 1 - n
したがって、私たちの目標は次のことを示すことです。
ログ(n)*n + 1 - n = O(ログ(n)*n)
明らかに、log(n)*n は O(log(n)*n) ですが、1-n?
1-n = O(log(n)*n)?
1-n <= k*log(n)*n、いくつかの k?
k = 1 とする
1-n <= log(n)*n?
両辺に n を加える
1 <= n*log(n) + n? はい
したがって、f(n) は O(n*log(n)) であることを示しました。
log(n) * n を使用して f(n) の上限を取得したので、log(n) * n を使用して f(n) の下限を取得してみましょう。
下限にはビッグ オメガ表記を使用します。Big Omega は、正の定数 k に対して関数 g(n)*k <= f(n) を探します。
k(n*log(n)) <= n*log(n) + 1 - n?
k = 1/10 とする
n*log(n)/10 <= n*log(n) + 1 - n?
(n*log(n) - 10n*log(n)) / 10 <= 1 - n?
-9n*log(n)/10 <= 1 - n? 10 を掛ける
-9n*log(n) <= 10 - 10n? -1 を掛ける (不等式の反転)
9n*log(n) >= 10n - 10? 9で割ります
n*log(n) >= 10n/9 - 10/9? n で割る
log(n) >= 10/9 - 10/9n ? はい
明らかに、量 log(n) は (10/9 - 10/9n) が 10/9 に近づくにつれて大きくなります。実際、n = 1 の場合、0 >= 10/9 - 10/9 です。0 >= 0。
これで、 が示されましたf(n) is Big-Omega(n*log(n))。これを の証明と組み合わせると、f(n) is O(n*log(n))が示されましたf(n) is Big-Theta(n*log(n))! （感嘆符は階乗ではなく興奮のためのものです...）
g(n) = n*log(n) であり、定数の有効なセットの 1 つはk1=1/10 (下限) およびk2 = 1 (上限) です。
big-O を証明するには:floor(log2(n)) + 1 = O(log(n))外側のループを通る反復があり、内側のループはO(n)あたり回、合計で. 回反復しO(n * log(n))ます。
ビッグ オメガを証明するには:floor(log2(n/2)) + 1 = Omega(log(n))外側のループを通る反復がありstep <= n/2ます。内側のループn + 1 - stepは回を繰り返しますが、これらの外側の繰り返しでは、per よりも多くn/2 = Omega(n)、合計でOmega(n * log(n)).
big-O と big-Omega を合わせて、big-Theta を証明します。
次のようにコードの表現を簡略化すると、コードをシグマ表記に変換できます
for (step = 1; <= n; step = step * 2) {
for(i = n; i >= step; step = step - 1) {
}
}
このような：
