大O，θ和欧米茄符号
我很困惑什么大的O，大的theta和大的omega代表着：最好的情况，最坏的情况和平均情况或上限和下限。
如果答案是上限和下限，那么上限和下限是什么？ 例如，让我们考虑一个算法。 那么对于最好的情况，小写的和平均的情况，它是否有三种不同的表达或增长率，并且对于每种情况我们都可以发现它是大的O，theta和omega。
最后，我们知道通过分而治之算法的合并排序具有n * log（n）的增长率或时间复杂度，那么它是最佳情况还是最坏情况的增长率，以及我们如何将大O，θ和欧米茄对此。 请你可以通过假设的表达来解释。
这些符号都是渐近渐近式的。 如果他们解释了最坏的情况，或者平均情况只取决于你所说的话。
例如，quicksort是一个用于排序的随机算法。 比方说，我们使用它确定性，并始终选择列表中的第一个元素作为枢轴。 那么存在长度为n的输入（对于所有n ），使得最坏的情况是O(n²) 。 但在随机列表中，平均情况是O(n log n) 。
所以我在这里用平均和最坏情况下的大O.
基本上这个表示法是为了简化。 如果你有一个5n³-4n²-3logn的算法，你可以简单地写出O(n³)并在n³之后摆脱所有的废话，并且忘记常量。
除了最大指数和所有常数因子（常数意味着它们不增长，但10100也是常数）之外，可以使用大O去除所有单项式。
最后，用O(f(n))一组函数，它们都有上界f(n) （这意味着g(n)在O(f(n)) ，如果你能找到常数c使得g(n) ≤ c⋅f(n) ）
为了使它更容易：
我已经解释过，大O意味着上限但不严格。 所以n³在O(n³) ，也是n² 。 所以你可以把大O看作是“较低的平等”。
你可以用其他方法做同样的事情。
小o是严格的低： n²是o(n³) ，但n³不是。
大欧米茄是一个“更大的平等”： n³是Ω(n³) ，也是n⁴ 。
小欧米茄是一个严格的“更大”： n³不在ω(n³)但n⁴是。
和大西塔大概是“平等”，所以N 3是Θ(n³)但既不n²也不n⁴是。
希望这会有帮助。
所以这个想法是O意味着“平均”，一个意味着最好的情况，一个意味着最坏的情况。 例如让我们想一想大多数排序算法。 如果物品已经按顺序排列，它们大多数会按n次排序。 你只需要检查他们是否有序。 他们都有最糟糕的订单，他们必须做大部分工作来订购一切。
链接地址: http://www.djcxy.com/p/39927.html