マスター定理を使用して再帰関係を解決しました。Θ(3n 2 -9n)まで下げました。これはΘ(n 2 )に等しいでしょうか? 解決策がΘ(2n 3 - 100 2 )である別の再発があります。BigTheta 表記では、常に最大の項のみを使用しますか? 2 つ目はΘ(n 3 )ですか? 2 番目のケースでは100n 2の方が重要なようです。では、捨てても問題ないでしょうか？
助言がありますか？
2373 次
2 に答える
2
はい。あなたの仮定は正しいです。1 つ目はΘ(n 2 )で、2 つ目はΘ(n 3 )です。Θ表記を使用している場合は、最大の項のみが必要です。
2 回目の再発の場合は、n = 1000n 3 = 1000000000を考慮してください。100n 2はちょうど100000000です。n の値が大きくなるにつれて、n 3が 100n 2よりもますます優勢になります。
理論的な目的では、定数がどれほど大きいかを考慮する必要はありません。ただし、実際のアプリケーションでは、複雑さが高くても、定数が小さいアルゴリズムが好まれる場合があります。たとえば、 nの値があまり大きくない場合は、 10000n 2の複雑さを持つアルゴリズムよりも、 0.01n 3の複雑さを持つアルゴリズムを使用する方がよい場合があります。
于 2013-04-21T17:03:24.040 に答える