这些算法中的哪一个需要更多时间？

Question

我有这些算法，但我没有找出哪个需要更多时间。

O((n^2)*log(n))

O(n*(2^n))

我计算了它们的对数，但我不明白哪个需要更多时间。

log((n^2)*log(n)) = 2log(n)+log(log(n))

log(n*(2^n))=log(n)+n*log(2)

Answer 1

第二个，因为：

2^n > n^2

和

n > log(n)

Answer 2

您可以计算、减少或简化这些表达式。

..但稍等一下，注意，有一个最高顺序操作数 2ⁿ，它增长 exponentially - 比你拥有的任何其他操作数更快（对于足够大的 n-s） - 即 n² 或 log₂n.

因此，O((n*(2ⁿ)) 对于足够大的输入来说会占用更多空间。

输入1→2操作
输入2→8次操作
输入3→24次操作
输入4→64次操作 ...
输入10 → 10240次操作

我想你能看出其中的规律。

注意，根据渐近分析，我们总是对大输入感兴趣，否则，对于 1、2 或非常小的输入，行为会有所不同。

Answer 3

数学不够好，无法证明，但只需为“n”填写一个值即可为您提供一个很好的指示。让我们取 n = 100，log 的底数是 10。

# First algorithm
100^2 * log(100) = 10000 * 2 = 20000

# Second algorithm
100 * 2^100 = 100 * 1267650600228229401496703205376 = 126765060022822940149670320537600

我认为总是选择第一种算法应该是很明显的。

Answer 4

对于 n 的小范围值（大约 n = 5 (~4.738) 到 26 (~25.783)）假设自然对数，第一个大于第二个，但大于第二个总是更大，并且随着 n 的增加而变得越来越大。

绘制它证实了这一点，这里使用 Mathematica:

f1[n_] := Log[n^2]*Log[n]
f2[n_] := Log[n*(2^n)]

Plot[{f1[n], f2[n]}, {n, 1, 50}]

这些算法中的哪一个需要更多时间？

which one of these algorithm take more time?

algorithm

execution