O(1/2 X log N) 是否等于 O(logN)？

Question

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

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

保存在N = M（N）= 1-[(logN) / 2 + 1] / [logN + 1] lim N→∞ M（N）= 1/2

这表明渐近地，我总会节省50％的内存。我困惑的是为什么我无法在大O分析中看到这种收益？

我的第二个问题是：如果我关于大O符号的理解是错误的，那么突出第二个算法版本中所节省的内存的正确方法是什么？

- ubaabd

---

Big-O 是关于可扩展性的，而你并没有改变这一点。 - Ben Voigt

不要把大O记法视为性能的唯一衡量标准。它从来就不是这样设计的。 - Patricia Shanahan

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³)，但在可能使用前者时，前者比后者更可取。

希望这能帮到你！

- templatetypedef

---

感谢您的回答。我刚刚意识到，即使在适度的N = 32k时，M(N) = .45也足以引以为豪。 - ubaabd

Answer 2

Big-O并不考虑常数因素，它只是衡量算法的扩展性 - 所以任何与log N成比例增长的内容都是O(log N)。这是一种相对度量，就像说两个人的薪水涨了10％一样，即使其中一个人的薪水从10,000增加到12,000，而另一个人的薪水从1,000,000增加到1,200,000。如果你被告知他们每年都得到10％的加薪，你不会期望知道某个人的总工资，所以如果你知道它的增长是O(log N)，就不要期望知道算法的总成本。

如果第二个版本的算法使用了一半的内存，但具有相同的扩展行为，则只需说它使用了一半的内存。

- Pete Kirkham

---

谢谢Pete。我认为在我的写作中，我应该只提到有限N的性能。 - ubaabd

Answer 3

大O表示法在确定算法或实现的可扩展性方面非常有用。常数的改进（在您的示例中为一半）仍然很有用，但当面对问题规模增加一个数量级时，它们的作用就不大了。

- Lord Peter