algorithm - 如何计算不同底数的对数项之和？

Question

我评估了一个具有运行时复杂性的算法，它遵循以下日志系列:

(log₂ n + 1) + (log₃ n + 2) + (log₄ n + 3) +.. ...+ (log_n n + (n - 1))

如何根据“大 O”表示法计算出该算法的时间复杂度？

Answer 1

分别考虑对数项和非对数项的总和。

log项中log₂ n最大，有n-1项。因此总和小于 (n-1)log₂ n，这是 O(n log n)。

非对数项的总和是 (n-1)n/2，这是 O(n²)。

我们看到非对数项的总和支配对数项的总和。因此，结果为 O(n²)。