运行时复杂度为θ（n^2）的运算复杂度为θ（n）的渐近运行时复杂度算法的运行速度总是比运行时间更快的运算时间？

Question

如果是的话，你能提供明确的例子吗？我知道像Quicksort这样的算法可以有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 $ as $ \ 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

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

程序的实际运行时间可能与渐近界很不一样。这是一个基本概念，它是由定义渐近符号的方式引起的。
你可以阅读我的回答here来澄清。