假设我有一个内存要求为 logN+1 的算法，其中 N 是问题的大小（要处理的位数）。我提出了第二个版本，将内存需求降低到 (logN)/2+1。我了解到在 Big-O 分析中忽略了常量，因此两个算法版本的复杂度都是 O(logN)。
现在，如果我计算使用第二版算法节省的内存，我得到
在 N = M(N) = 1 - [(logN)/2+1]/[logN+1]
lim N→∞ M(N) = 1/2时节省的内存
这表明渐近地我将始终节省 50% 的内存。我很困惑为什么我无法在 Big-O 分析中看到这种收益？
我的第二个问题是：如果我对 Big-O 表示法的理解是错误的，那么突出显示算法第二版中保存的内存的正确方法是什么？
请记住，大 O 表示法不包括常数因子。函数 f(n) = n 和 g(n) = 10 100 n 都是 O(n)，尽管 f(n) 是一个比 g(n) 小得多的函数。
您的分析是正确的 - 如果您可以使空间使用量 (log n) / 2 - 1，那么您将（在限制范围内）将所需的内存量减半。但是，这不会出现在大 O 分析中，因为大 O 忽略了常数因素。正如在其他一些答案中所提到的，大 O 表示法捕获了长期增长率，尽管常量可能会告诉您更多关于使用的空间的绝对量，但常量并不能控制空间使用的长期增长率.
如果你想做更精确的分析，你可以给出之前和之后的确切内存使用情况，然后说你已经减少了 50% 的内存使用情况。许多关于算法和数据结构的论文实际上确实包含了常数因素，并提到它们正在获得不断的加速。例如，Cholesky 分解算法和高斯消元算法都给出了求解线性系统的 O(n 3 ) 算法，但是当可以使用 Cholesky 分解时，它的运算量减少了大约 50%。大多数涵盖这些主题的教科书都会提到，尽管两种算法都是 O(n 3 )，但如果可以使用前者，则前者比后者更可取。
希望这可以帮助！
Big-O 没有考虑常数因素。它只是衡量算法如何扩展的量度 - 所以任何与 log N 成比例增长的东西都是 O(log N)。这是一个相对的衡量标准，就像说两个人加薪 10%，即使一个人的工资从 10,000 到 12,000，另一个从 1,000,000 到 1,200,000。如果你被告知某人的总工资每年增长 10%，你就不会指望知道他们的总工资是多少，所以如果你知道算法的总成本增长 O(log N)，就不要指望知道它的总成本.
如果算法的第二个版本使用了一半的内存但具有相同的缩放行为，那么简单地说它使用了一半的内存。
Big-O 在确定算法或实现如何扩展方面非常有用。常数的改进（在您的示例中是一半）仍然有用，但是当问题大小增加一个数量级时，它们几乎没有效果。