algorithm - 算法最坏情况运行时间的上限与下限

Question

我正在学习算法分析。我了解算法的最坏情况运行时间的概念。

但是，算法最坏情况运行时间的上限和下限是多少？

什么是算法最坏情况运行时间的上限与最坏情况运行时间的下限不同的例子算法？

Answer 1

对于函数 f(n) , g(n)是一个上限 ( big O ) 如果对于“足够大的 n”, f(n)<=c*g(n) , 对于常量 c . [g 支配 f]
g(n) 是下限 ( big Omega ) 如果对于“足够大的 n”，f(n) >= c*g(n) , 对于常量 c . [f 支配 g]

如果g(n)是f(n)的上限和下限[具有不同的 c]，我们说 g(n) 是 f(n) [Big theta] 的紧界

使用上界示例代替紧界:有时很难找到紧界，例如 fibonacci递归算法。所以我们很容易找到 O(2^n) 的上界。更多信息可在此 post 的答案中找到.

它与最差/基本/...情况有何关系？(根据评论要求):

最坏情况/平均情况(或任何其他情况)会影响复杂度函数，但大 O、大 Omega 和大 Theta 可以应用于这些情况中的每一种。

例如，一个 HashTable 插入是 Θ(1)插入平均大小写，以及 Θ(n)最坏情况插入。也是O(n)平均大小写插入(绑定(bind)不紧)，以及 Ω(1)最坏情况插入。