algorithm - 同一算法的不同上界和下界

Question

所以我刚开始学习算法的渐近界
问题：如果我们发现算法的下界和上界不同，关于函数的θ我们能说什么？（比如 omega(n) 和 O(n^2)）。或者更确切地说，对于这种算法的紧密性，我们能说些什么？

我读的书说 Theta 是函数的相同上限和下限。在这种情况下呢？

Answer 1

在那种情况下，我认为你不能说什么。

的定义Θ(f(n))是：

一个函数是Θ(f(n))当且仅当它是Ω(f(n))and O(f(n))。

对于某些表现出这些行为的病理功能，例如在n和之间振荡n^2，它不会被定义。

例子：

f(x) = n if n is odd
       n^2 if n is even

您的界限Ω(n)会O(n^2)很严格，但Θ(f(n))没有为任何功能定义。

另请参阅：Θ(n) 和 O(n) 有什么区别？

Answer 2

只是为了一点实用性，一种不Θ(f(n))适用的算法是f(n)插入排序。它运行是Ω(n)因为对于已经排序的列表，您在每个步骤中只需要一个插入操作，但它在O(n^2)一般情况下运行。构造振荡或不连续的函数通常用于教学目的，但根据我的经验，这种函数很少出现在实际算法中，如果有的话。

关于紧密度，我只听说过在这种情况下参考为算法提出的上限和下限。再次关于插入排序的示例，从某种意义上说，给定的界限是严格的，即存在实际上可以在时间上线性地完成的问题实例（下限）和其他不会执行的问题实例时间小于其大小的二次方。有效但对插入排序不严格的边界是Ω(1)因为您无法在恒定时间内对任意大小的列表进行O(n^3)排序，并且因为您始终可以n在严格的时间内对元素列表进行排序O(n^2)，这要少一个数量级，所以你当然可以做到O(n^3). bounds 的目的是让我们大致了解我们可以预期算法的性能，以便我们了解我们的解决方案的效率；紧边界是最可取的，因为它们都给我们提供了粗略的想法，并且从某种意义上说，这种想法是最优的，因为在极端情况下（有时也是一般情况），我们实际上需要边界允许的所有复杂性。

平均案例复杂度没有限制；它“仅”描述了算法“在大多数情况下”的效率；以快速排序为例，它的最佳情况复杂度为Ω(n)，最坏情况复杂度为O(n^2)，平均情况复杂度为O(n log n)。这告诉我们，对于几乎所有情况，快速排序与一般情况下的排序一样快（即平均情况复杂度），而在某些情况下它解决的问题比这更快（最佳情况复杂度 -> 下限）和还有一些需要快速排序才能解决的问题的实例（最坏情况复杂性 -> 上限）。