大O表示法 用于访问链表和二分查找中的中间元素？

Question

文章位于 http://leepoint.net/notes-java/algorithms/big -oh/bigoh.html 表示访问链表中的中间元素的大 O 表示法是 O(N) 。不应该是 O(N/2) 。假设我们在链表中有 100 个元素所以访问第 50 个元素必须从第一个节点向右遍历到第 50 个。因此操作次数将在 50 左右。

为二分查找定义的另一大符号是 log(N)。假设我们有 1000 个元素。根据 log(N)，我们将需要接近 3 的运算。现在让我们手动计算，下面将是模式

第 500 个元素、第 250、125、63、32、16、8、4、2，因此运算约为 9它比 3 大得多。

我在这里缺少什么吗？

Answer 1

O(n) 表示“对于所有较大的 n，与 n 成比例”。¹

所以它不必等于n。

编辑：

我上面的解释有点不清楚 O(n) 中的某些内容是否也在 O(n²) 中。它是 - 我对“比例”这个词的使用很差，正如其他人试图提到的那样（正如我最初的误解一样），“收敛”将是一个更好的术语。²

_{1：它实际上意味着“在最坏的情况下，当n很大时，与n成比例-案例场景”，但书籍通常会考虑“平均”情况，更准确地表示为 f(n) ~ n，其中 f 是您的函数。}

_{2：更多技术人员：这应该是显而易见的，但我不打算在数学上严谨。如果您正在寻找形式证明（带有比率、限制等），Math.SE 可能是提出这个问题的更好选择。}

Answer 2

从您链接的网页：

同样，常量乘数也被忽略。所以 O(4*N) 算法是
等价于 O(N)，这就是它应该写的。最终你
在确定时要注意这些乘数
性能，但对于使用 Big-Oh 的第一轮分析，您
简单地忽略常数因素。

Answer 3

Big O 表示法是算法效率的通用表达。您不应将其解释为算法速度或需要多少内存的精确方程，而应将其视为近似值。函数的常数乘数将被忽略，因此例如您可以将示例视为 O 1/2(N) 或 O k(N)，删除 k这给你 O(N)。

Answer 4

你缺少的是任何常数倍数对于 Big O 来说都不重要。所以我们有 O(N) = O(N/2)。

关于问题的 log 部分，它实际上是 log₂(N) 而不是 log₁₀(N)，所以在这种情况下 log(1000) 实际上是 9 （当向下舍入）。另外，和以前一样，O(log₂(N)) = O(log₁₀(N))，因为两者只是彼此的常量倍数。具体来说，log₂(N) = log₁₀(N) / log₁₀(2)

最后要考虑的是，如果有几个函数相加在一起时，低阶函数与 Big O 无关。这是因为高阶函数比低阶函数增长得更快。所以我们发现 O(N³ + N) = O(N³) 和 O(e^N + N ² + 1) = O(e^N)。

因此需要考虑两件事：删除倍数和删除低次函数。