私はBigO表記について学び始めたばかりで、アルゴリズムの成長率を計算する方法について質問がありました。時間計算量がO（√nlogn）のアルゴリズムがあり、n=10の場合のアルゴリズムは2秒かかるとします。n = 100の場合にかかる時間を知りたい場合は、2 / x =（√10log10）/（√100log100）の比率を設定してから、xを解きますか？または、入力が10倍大きいので、2 *（√10log10）秒かかると言えますか？
質問する
2302 次
1 に答える
2
最初の方法が正しいです。Big O は定数の倍数を気にしないので、定数を代数で解くことで決定できます。
c*(√10*log(10)) = 2
c = 2/(√10*log(10))
√100*log(100) * 2/(√10*log(10)) = x
ただし、大きな O は「小さい」項も気にしないことに注意してください。したがって、これらの一定のオーバーヘッドとその他の小さいスケーリング係数は、この計算を漸近的に正確にするだけです。たとえば、次の方程式によって管理されるアルゴリズム:
(√n log n + 1/n) = t
はまだ O(√n log n) であり、これにより n の値が小さい場合、計算の精度が低下します。
于 2013-01-30T18:23:13.993 に答える