algorithm - 是 O(1/2 X log N) = O(logN)

Question

假设我有一个内存需求为 logN+1 的算法，其中 N 是问题的大小(要处理的位数)。我提出了第二个版本，将此内存需求减少到 (logN)/2+1。我了解到在 Big-O 分析中常量被忽略，所以两个算法版本的复杂度都是 O(logN)。

现在，如果我计算使用第二版算法节省的内存，我得到

Memory saved at N = M(N) = 1 - [(logN)/2+1]/[logN+1]
lim N→∞ M(N) = 1/2

这表明渐近地我将始终节省 50% 的内存。我很困惑，为什么我在 Big-O 分析中看不到这种 yield ？

我的第二个问题是:如果我对 Big-O 表示法的理解是错误的，那么突出显示第二版算法中保存的内存的正确方法是什么？

Answer 1

请记住，大 O 表示法不包括常数因子。函数 f(n) = n 和 g(n) = 10¹⁰⁰n 都是 O(n)，尽管 f(n) 比 g(n) 小得多。

您的分析是正确的 - 如果您可以使空间使用量 (log n)/2 - 1，那么您将(在极限范围内)将所需内存量减半。然而，这不会出现在大 O 分析中，因为大 O 忽略了常数因子。正如其他一些答案中提到的，大 O 表示法捕获长期增长率，尽管常量可能会告诉您更多关于所用空间的绝对量，但常量并不能控制长期 -空间使用率的长期增长率。

如果你想做更精确的分析，你可以给出前后的确切内存使用量，然后说你减少了50%的内存使用量。许多关于算法和数据结构的论文实际上都包含常数因子，并提到它们正在获得恒定的加速。例如，Cholesky factorization算法和高斯消元法都给出了求解线性系统的 O(n³) 算法，但是当可以使用 Cholesky 分解时，它的运算量减少了大约 50%。大多数涵盖这些主题的教科书都会提到，尽管这两种算法的复杂度均为 O(n³)，但在可能的情况下，前者优于后者。

希望这对您有所帮助!