algorithm - 入力サイズに基づいてアルゴリズムの時間ステップ数を見つける

Question

入力サイズ 1000 で O(log n) アルゴリズムを実行し、アルゴリズムが 110 回の操作を必要とするとします。入力サイズを 2 倍の 2000 にすると、アルゴリズムには 120 回の操作が必要になります。入力サイズを 2 倍の 4000 にした場合に必要な操作の数について、最も適切な推測はどれくらいですか?

Answer 1

ソリューションには、実行時のオーバーヘッドに対応する追加の定数があります。以下では、結果が O(log n) ではなく Ɵ(log n) であると仮定しています。

一般化された予測を行いたい場合は、引き続き定数を明示的に解くこともできますが、2 つの点に基づいてそうするのはかなり疑わしいでしょう。

Answer 2

を操作数の見積もりにしましょうf(n)。質問を式に入れるだけです。

f(n) = c * log(n) // O(log n) algorithm
f(1000) = 110
f(2000) = 120
f(4000) = ?

見つけcて、答えを見つけてください。しかしもちろん、これは与えられたデータと の制限動作に基づいた最良の推測fにすぎません。

複数の理由により、正確な予測にはなりません。

• 大きなO表記は、実際の複雑さの式ではなく、アルゴリズムの複雑さの制限動作を提供するだけです。
• 操作の回数は、多重度だけでなく、データの性質に強く依存する場合がありますn。
• 制限動作は、可能なデータの特定のケース (通常は最悪のケース) で計算されます。