Question

a

【計算量】
表の求め方分かりますか？
また、2^nについては、小数点をどうするのかが分かりません。

問題2.4.4 ★★
次の表は「Nがどの程度の大きさであればおおよそ何回の計算を行うか」 を表したものです。 この表
を完成させてください。 なお、 計算回数の定数倍 (例:10№2 の "10" の部分)は考えないものとします。
また、 logの底は2であるものとします。
計算回数
実行時間目安
N log N
N2
2N
10°回以内
0.001 秒以下
N≤ 60,000
N ≦ 1,000
N≤ 20
107 回以内
0.01秒以下
10°回以内
0.1秒以下
10°回以内
1秒以下

問題 2.4.4
答えは以下のようになります。 なお、 N log N は N × log N と同じ意味です。
計算回数
N log N
N2
2N
N≤ 60000
N ≤ 1000
N ≤ 20
106回以内
107 回以内
N ≤500000
N ≤3000
N ≤ 23
10°回以内
N ≤ 4000000
N ≤ 10000
M≤ 26
10°回以内
N≤ 40000000
N ≤30000
N ≤30