big-o - 渐近运行时复杂度为 θ(n) 的算法是否总是比运行时复杂度为 θ(n^2 ) 的类似算法更快？

Question

如果是这样，你能提供明确的例子吗？我知道像快速排序这样的算法可以有 O(n log n) 的预期运行时间，但在更坏的情况下是 O(n^2)。我假设如果预期/最坏情况的相同原则适用于 theta，那么上述问题可能是错误的。了解 theta 的工作原理将帮助我理解 theta 和 big-O 之间的关系。

Answer 1

当$n$足够大时，复杂度$\theta(n)$的算法将比复杂度$\theta(n^2)$的算法运行得更快。实际上 $\theta(n) / \theta(n^2)\to 0$ 为 $\theta\to \infty$。然而，可能存在 $n$ 的值，其中 $\theta(n) > \theta(n^2)$。

Answer 2

它并不总是更快，只是渐近更快（当n无限增长时）。但经过一段时间n——是的，它总是更快。

例如，n冒泡排序可能比快速排序运行得更快，因为它更简单（它的θ常数较低）。

这与预期/最坏情况无关：选择一个案例是另一个与 theta 或 big-O 无关的问题。

关于 theta 和 big-O 之间的关系：在计算机科学中，big-O 经常（误）用于 θ 的含义，但严格意义上来说，big-O 是一个比 θ 更广泛的类：它只限制了上一个增长函数的边界，而 theta 限制了两个边界。例如，当有人说 Quicksort 的复杂度为 O(n log n) 时，他实际上是指 θ(n log n)。

Answer 3

你走在正确的思想轨道上。

程序的实际运行时间可能与渐近界完全不同。这是一个基本概念，源于渐近符号的定义方式。您可以在此处
阅读我的答案以进行澄清。