-1

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

4

3 回答 3

0

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

于 2013-07-15T21:43:06.153 回答
0

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

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

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

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

于 2013-07-15T21:47:08.983 回答
0

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

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

于 2013-07-17T09:37:00.613 回答