c - n=10 のプログラムを 2 秒で実行すると、n=100 を実行するのに何時間かかりますか?

Question

n=10 のプログラムが 2 秒で実行される場合、複雑さ n * log(n) で n=100 を実行するにはどれくらいの時間がかかりますか? 考えてみたら多分4秒だと思うんだけど、どうやって証明すればいいの？

Answer 1

かかる時間が単なる上限ではなく、n*log(n) に正確に比例すると仮定すると ( http://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notationsを参照)、次のようになります。

executionTime = (constant) * n * log(n)

n=10 を代入して定数を求めます。これで、n ごとの実行時間の式ができました。

Answer 2

さて、次のことを考慮してください。

線形の場合、つまり O(n) の場合、2 秒で 10 の操作が完了するため、n操作は 10 の操作を意味します。

==> 10 * k = 2s
==> k = 0.2 (seconds per operation)

O(n*log(n)) の複雑さ (つまり、Big-Oh) では、次のような多くの操作が必要になります。

==> n * log(n)
==> 100 * log(100)
==> 100 * 2 = 200

ここで、0.2 秒/オペレーション、200 オペレーション、複雑さ O(n*log(n)) のアルゴリズムを使用すると、次のようになります。

==> T = 0.2s/operation * 200 operations = 40 seconds

これはかなり良い結果です。線形の場合 (つまり、O(n))、節約はそれほど良くありません。

==> T = 0.2s/operation * 100 operations = 20 seconds

これが O(n^2) の場合、恐ろしいことになります。

==> T = 0.2s/operation * (100^2) = 0.2*10,000 = 2000 seconds

お役に立てれば！

Answer 3

n=10 の場合、最悪の場合、プログラムは 10*log(10) = 10 回の操作を行います。

n=100 の場合、100*log(100) = 200 回の操作が必要です。

10 operations  --> 2 seconds
200 operations --> X seconds

X = 40 second.