algorithm - アルゴリズムの時間計算量

Question

サイズ n=100 のアルゴリズムの実行には 21 秒かかります。サイズ n=1000 の場合、実行に 31 秒かかり、n=10000 の場合、実行に 41 秒かかります。実行の複雑さは何ですか?

O(n) を試した場合: T(n)=(21*1000)/100 = 210 s (O(n) ではない)
O(n^2) を試した場合: T(n)=(21* 1000^2)/100^2 = 2100 秒 (O(n^2) ではありません)
O(log n) を試してみると: T(n)=(21*log1000)/log100=31.5 (O(log n ではありません) )))

私が与えられた他のオプションは O(1/n) です。これを計算するにはどうすればよいですか？

Answer 1

のように見えますO(lgn)。

対数の底が10のときの時間ですn。T(n) = 10*log(n) + 1

Answer 2

この問題を解決するには、さまざまなクラスの関数をプロットすることから始めます。たとえば、O(n)線形クラスプロット関数T(n)=nについて学習し、O(n^2)クラスプロット関数について学習しますT(n)=n^2。これは、さまざまな機能の形を認識するのに役立ちます。

その後、質問で与えられたポイントを、x軸にnの値、y軸に時限値を使用してプロットします。この質問では、形をすばやく認識できるはずです。

ヒント：そうではありませんO(log n) :-)