algorithm - 如何使用大 O 计算增长率？

Question

我刚刚开始学习 Big O 表示法，并且有一个关于如何计算算法增长率的问题。假设我有一个时间复杂度为 O(√n log n) 的算法，并且对于 n = 10，我的算法需要 2 秒。如果我想知道 n = 100 需要多长时间，我是否设置了一个比率，其中 2/x = (√10 log 10)/(√100 log 100) 然后求解 x？或者我可以说我的输入是 10 倍大，所以需要 2*(√10 log 10) 秒？

Answer 1

第一种方法是对的。Big O 不关心常数倍数，因此您可以通过代数求解来确定常数。

c*(√10*log(10)) = 2
c = 2/(√10*log(10))
√100*log(100) * 2/(√10*log(10)) = x

但是，请记住，大 O 也不关心“较小”项，因此那些恒定的开销和其他较小的比例因子只会使这个计算渐近准确。例如，由以下等式控制的算法：

(√n log n + 1/n) = t

仍然是 O(√n log n)，这将使您的计算对于较小的 n 值不太准确。