c - 如果程序在 n=10 的情况下在 2 秒内执行，那么执行 n=100 需要多少时间？

Question

如果一个程序在 n=10 的情况下在 2 秒内执行，那么执行 n=100 的复杂度为 n * log(n) 需要多少时间？我想了想，我认为可能是 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

好吧，考虑以下几点：

线性情况下 2 秒内完成 10 次操作，即：O(n)，所以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.