performance - 比较以复杂形式表示的算法运行时间

Question

我知道如何比较不同算法的运行时间。

有时很明显，有时需要简化，有时除法并使用 L'Hopital 规则来查看它是否收敛到一个常数或 0。

但是，如果它们是复杂的形式，你如何比较它们呢？

例如，你会如何比较

和n？

当然，我想要一个严格的证明。

Answer 1

在这个例子中，第一个简化是去掉sqrt(2)-0.4电源。这种力量是如此接近，1以至于几乎没有什么不同。如果您的比较需要这种区别，我们深表歉意。这可能有一个求幂规则，但我记不清我的数学了。

接下来是使用 log 规则来分解log ₉₆ n。

等效值为log ₂ n / log ₂ 96。现在你有2到前者的力量。 log ₂ 96只是一个常数（大约 6.585）。您可以将其排除在外（因为它随着n增加而变得微不足道），或者将其保留并使用另一个日志规则。让我们把它留在：

log ₂ n / log ₂ 96变为log ₂ n ^{(log ₂ 96) -1}

整个事情简化为n ^{(log ₂ 96)-1}。或者，如果您进行了额外的简化，您将得到2 ^ log ₂ n，即n。

由于您想与 n 进行比较，因此第一个结果似乎更相关，大约为0.15n。

Answer 2

它对每个问题都是特定的。在这种情况下，假设 n = 96^k 和 96 = 2^m。

n vs 表达式可以重写为：

2^(m*k) vs 2^(k ^(sqrt(2) - 0.4))

由于 2, m, k, sqrt(k) - 0.4 都 > 0，所以比较变成

(m * k) vs k ^(sqrt(2) - 0.4)

或者

m vs k ^(sqrt(2) - 1.4) 

但是 m = log 96 以 2 为底，这是固定的 (6.585) 而 k 是无界的

因此表达式 (RHS) 会更大。