DrS*_*ove 3 big-o time-complexity
每个算法都有大欧米茄？
算法是否有可能同时具有Big O和Big Omega(但彼此不相等 - 不是Big Theta)？
例如Quicksort的Big O - O(n log n)但是它有Big Omega吗？如果是的话,我该如何计算呢？
首先,最重要的是不要将约束与案件混为一谈.一个必然 -像大哦,大欧米茄,大西塔等-说一些关于增长的速度.一个案例说明了您目前正考虑通过算法处理的输入类型.
让我们考虑一个非常简单的例子来说明上面的区别.考虑规范的"线性搜索"算法:
LinearSearch(list[1...n], target)
1. for i := 1 to n do
2. if list[i] = target then return i
3. return -1
人们可能会考虑三种广泛的案例:大小输入的最佳,最差和平均情况n.在最好的情况下,您要查找的是列表中的第一个元素(实际上,在列表开头的任何固定数量内).在这种情况下,找到元素并从函数返回只需要一些恒定的时间.因此,对于最好的情况,Big-Oh和Big-Omega恰好相同:O(1)和Omega(1).我们也说,当两者O同时Omega适用时,这也是Theta如此Theta(1).
在最坏的情况下,元素不在列表中,并且算法必须遍历所有n条目.因为f(n) = n碰巧是一个函数,它是由同一类函数(线性函数)从上方和下方绑定的,所以这是Theta(n).
平均案例分析通常有点棘手.我们需要为可行的长度输入定义概率空间n.可以说所有有效输入(例如,整数可以使用无符号模式中的32位表示)同样是可能的.由此可以得出算法的平均性能如下:
target列表中未显示的概率.乘以n.target列表中至少有一次,找到它在k每个位置出现的概率1 <= k <= n.每个乘以P(k)通过k.n.请注意,在上面的步骤1中,如果概率非零,我们肯定会得到至少一个线性函数(练习:我们永远不会超过线性函数).但是,如果步骤1中的概率确实为零,则步骤2中概率的分配在确定复杂性方面有所不同:对于某些分配,您可以具有最佳情况行为,对于其他分配,最坏情况可能最终,并且可能最终行为与最佳(恒定)或最差(线性)不同.
有时候,我们可能会松散地谈论"一般"或"普遍"的情况,它会考虑所有类型的输入(不仅仅是最好的或最差的),但是这并没有给输入任何特定的权重,也没有取平均值.换句话说,您可以根据最坏情况的上限和最佳情况的下限来考虑算法的性能.这似乎就是你正在做的事情.
唷.现在,回到你的问题.
是否有具有不同的功能O和Omega界限？当然.考虑以下功能:
f(n) = 1 if n is odd, n if n is even.
最好的情况是" n很奇怪",在这种情况下f是Theta(1); 最坏的情况是" n是偶数",在这种情况下f是Theta(n); 如果我们假设我们正在谈论的32位无符号整数平均情况下,则f是Theta(n)在平均情况下,也是如此.但是,如果我们谈论"普遍"的案例,那么f就是O(n)和Omega(1),而不是Theta任何事情.运行时行为符合的算法f可能如下:
Strange(list[1...n], target)
1. if n is odd then return target
2. else return LinearSearch(list, target)
现在,一个更有趣的问题可能是是否存在一些算法(某些情况除了"通用"情况)不能分配一些有效的Theta约束.这很有意思,但并不过分.原因是您在分析期间可以选择构成最佳和最坏情况行为的案例.如果你对案件的第一选择结果是没有Theta约束,你可以简单地排除出于你的目的"异常"的输入.在这个意义上,案例和界限并不是完全独立的:你通常可以选择一个案例,使其具有"好"的界限.
但你能一直这样做吗？
我不知道,但这是一个有趣的问题.
是的。大欧米茄是一个下界。可以说任何算法至少需要常数时间，因此任何算法都是?(1)。
不。Big O 是一个上限。不（可靠地）终止的算法没有大 O。
如果我们可以说，在绝对最坏的情况下，算法不会花费比这更长的时间，那么算法有一个上限。我很确定O(?)不是有效的符号。
实际上有一个特殊的符号表示它们何时可以相等： Big Theta (?)。
如果算法与输入的大小完美地缩放（意味着没有输入大小，算法突然变得更有效率），它们将相等。
这是假设我们将 Big O 作为最小可能的上限，Big Omega 作为最大可能的下限。这实际上不是定义所要求的，但它们通常被非正式地视为这样。如果你放弃这个假设，你会发现一个 Big O 和 Big Omega 对于任何算法都不相等。
蛮力素数检查（我们只是遍历所有较小的数字并尝试将它们分成目标数）可能是最小上限和最大下限不相等的一个很好的例子。
假设您有一些数字n。让我们暂时忽略这样一个事实，即更大的数字需要更长的时间来划分（当我们考虑到这一点时，类似的论点成立，尽管实际的复杂性会有所不同）。而且我还根据数字本身而不是数字的大小来计算复杂性（可以是位数，并且可能会改变这里的分析）。
如果n可被 2（或其他一些小素数）整除，我们可以非常快速地检查它是否是 1 个除法（或恒定除法次数）的素数。所以最大的下限是?(1)。
现在，如果n是质数，我们需要尝试除以n每个数字sqrt(n)（我将把我们不需要高于这个的原因作为练习）。这将需要O(sqrt(n))，这也将是我们的最小上限。
所以算法将是?(1)和O(sqrt(n))。
对于一些特别复杂的算法，精确的复杂度也可能难以计算。在这种情况下，简单地计算一些合理接近的下限和上限并保持不变可能会更容易和可接受。但是，我手头没有这方面的示例。
不要混淆最好和最坏情况的上限和下限。这是一个常见的错误，有点令人困惑，但它们并不相同。这是一个完全不同的主题，但作为一个简短的解释：
可以为每个输入大小计算最佳和最差（和平均）情况。然后可以将上限和下限用于这 3 种情况中的每一种（单独）。您可以将这些情况中的每一种视为图形上的一条线，输入大小在 x 轴上，时间在 y 轴上高于或低于该线，因为输入大小趋于无穷（这不是 100% 准确，但这是一个很好的基本想法）。
快速排序有一个最坏的情况（当我们在每一步都选择最糟糕的支点时）和最好的情况（当我们选择好的支点时）。请注意 Big Theta 的使用，这意味着它们中的每一个都是下限和上限。?(n2)?(n log n)
让我们将快速排序与上述质数检查算法进行比较：
n，并且n是 53。由于它是素数，因此它（总是）会采取一些sqrt(53)步骤来确定它是否是素数。所以最好和最坏的情况都是一样的。n，并且n是53现在那些53元，可以设置成快速排序结束采摘非常糟糕的基点和奔跑在周围的步骤（最坏情况下）或者真正好的支点和奔波步骤（最好的情况）。所以最好和最坏的情况是不同的。53253 log 53n将上述每一项都设为 54：
1一步即可确定 54 是质数。最好和最坏的情况再次相同，但它们与 53 时的情况不同。54254 log 54因此，对于快速排序，最坏的情况总是需要几个步骤，而最好的情况总是需要几个步骤。因此，最坏情况的下限和上限（或“紧”）界限是，而最好情况的紧界限是。n2n log n?(n2)?(n log n)
对于我们的主要检查，有时最坏的情况需要大约sqrt(n)步骤，有时需要大约1步骤。因此，最坏情况的下限是?(1)，上限是O(sqrt(n))。最好的情况也是如此。
Note that above I simply said "the algorithm would be ?(1) and O(sqrt(n))". This is slightly ambiguous, as it's not clear whether the algorithm always takes the same amount of time for some input size, or the statement is referring to one of the best, average or worst case.
It's hard to give general advice for this since proofs of bounds are greatly dependent on the algorithm. You'd need to analyse the algorithm similar to what I did above to figure out the worst and best cases.