2

入力サイズが 100 の場合、アルゴは 0.5 ミリ秒かかります。入力サイズが 500 で、プログラムが O(n lg(n)) の場合、実行にかかる時間はどれくらいですか?

私の本によると、入力サイズが 2 倍になると、n lg(n) は「2 倍より少し長い」時間がかかります。それは本当に私を助けていません。

私が行ってきた方法は、定数乗数を解決することです（本では説明されていないため、有効かどうかはわかりません）：

.5ms = c * 100 * lg(100) => c = .000753

そう

.000753 * 500 * lg(500) = 3.37562ms

それは実行時間を計算する有効な方法ですか?それを把握するためのより良い方法はありますか?

4

2 に答える 2

1

それは正確には正しくありません。Tomasは、オーバーヘッドがあり、実際の方程式はより似ていると言ったのは正しかったです。

runtime = inputSize * lg(inputSize) * singleInputProcessTime + overhead

singleInputProcessTimeは、アドレススペースの読み込み、算術演算など、入力を操作するたびに実行する必要のあるすべてのマシン操作と関係があります。これには通常、ドメインに応じて数CPUサイクルから数秒または数分の範囲のランタイムがあります。この時間はほぼ一定であるため、入力サイズが大きくても全体の実行時間にはあまり影響しないことを理解することが重要です。

オーバーヘッドは、アルゴリズムをメモリに読み込む、サーバー/プロセス間で入力を分散する、入力サイズに依存しない1回または設定された回数だけ発生する必要がある操作など、問題/解決策を設定するためのコストです。このコストも一定であり、問​​題の解決に使用された方法に応じて、数CPUサイクルから数分までの範囲になります。

inputSizeとn*lg（n）はすでに知っていますが、宿題の問題については、どのようにして解決策にたどり着いたかを説明している限り、問題はありません。

于 2009-10-06T18:01:06.873 に答える
1

はい。それがまさにその仕組みです。

もちろん、これはbig-o表記で指定されていないため、考えられる初期化オーバーヘッドを無視しますが、ほとんどのアルゴリズムには関係ありません。

于 2009-10-02T18:21:40.960 に答える