1

次の解決策が正しいかどうか誰か教えてもらえますか?

t(n) = t(n-2) + (n-2)²の実行時間を計算しようとしています

さらに評価する

=> t(n)=t(n-4) + (n-2)² + n²

=> t(n)=t(n-6) + (n-6)² + (n-2)² + n²

...これは 2 だけ減っているので、約 n/2 項になり、すべての正方形を展開すると (n/2) * (n²) となり、これは n³ に等しくなります。したがって、実行時間はtheta(n³)です。

これは正しい解決策ですか？

4

2 に答える 2

3

はい、上記は完全に正しいです (最初の行のわずかな例外を除いt(n) = t(n-4) + (n-4)^2 + (n-2)^2て、問題の定義に従って、それに続くものを修正する必要がありますが、漸近的な結果には影響しません)。

これを証明するために、数学的帰納法を使用できます。

Claim: t(n) <= n^3
base: T(2) = 2 (assumption - otherwise we'll get stuck)
let's assume the assumption is true for each n<k for a certain k.
t(k) = t(k-2) + (k-2)^2 <= (k-2)^3 + (k-2)^2 = 
     = k^3 -6k^2 + 12k -8 + k^2 - 4k + 4
     = k^3 -5k^2 + 8k - 4

あとはそれを示すだけで5k^2 >= 8k - 4、完了です。方程式はそれぞれに当てはまりますk>=2- それが練習問題として残されていることを証明しています。

上記から、t(n) is in を導き出すことができますO(n^3)。同様のアプローチを使用して、それが にもあることを示すことができますOmega(n^3)。Theta(n^3)

于 2012-09-22T07:36:02.963 に答える
2

このオンライン計算機を使用すると、結果として Θ(n^3) を確認できます。

n^3

私が思うに、正しい乗算は Θ(n^3) を作成します。

于 2012-09-22T07:35:54.437 に答える