4

每个算法都有Big Omega吗？

算法是否有可能同时具有大 O 和大欧米茄（但不等于彼此 - 不是大 Theta）？

例如 Quicksort 的 Big O - O(n log n) 但它有 Big Omega 吗？如果是，我该如何计算？

4

3 回答 3

9

首先，最重要的是不要将绑定与案例混淆。一个界限——比如 Big-Oh、Big-Omega、Big-Theta 等——说明了增长率。一个案例说明了您当前正在考虑由您的算法处理的输入类型。

让我们考虑一个非常简单的例子来说明上面的区别。考虑规范的“线性搜索”算法：

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 位表示）都是同样可能的。由此，可以计算出算法的平均性能如下：

  1. target找出未在列表中表示的概率。乘以n。
  2. 鉴于它target在列表中至少出现一次，求它出现在k每个位置的概率1 <= k <= n。将每个P(k)乘以k。
  3. 将以上所有内容相加得到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)and 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限制，您可以简单地排除出于您的目的“异常”的输入。从这个意义上说，案例和界限并不是完全独立的：您通常可以选择一个案例，使其具有“良好”界限。

但你能一直做到吗？

我不知道，但这是一个有趣的问题。

于 2013-03-07T17:01:30.303 回答
7

每个算法都有一个大欧米茄吗？

是的。Big Omega 是一个下界。可以说任何算法都至少需要恒定的时间，所以任何算法都是Ω(1).

每个算法都有一个大 O 吗？

不，大 O 是一个上限。不（可靠）终止的算法没有大 O。

如果我们可以说，在绝对最坏的情况下，算法不会花费比这更长的时间，那么算法就有上限。我很确定O(∞)这不是有效的表示法。

算法的大 O 和大欧米茄何时会相等？

实际上有一个特殊的符号表示它们何时可以相等： Big Theta (Θ)。

如果算法与输入的大小完美地缩放，它们将是相等的（这意味着算法没有突然变得更有效率的输入大小）。

这是假设我们将 Big O 视为可能的最小上限，并将 Big Omega 视为可能的最大下限。定义实际上并不要求这样做，但它们通常被非正式地对待。如果你放弃这个假设，你会发现对于任何算法都不相等的大 O 和大欧米茄。

强力素数检查（我们只是循环遍历所有较小的数字并尝试将它们划分为目标数字）可能是最小上限和最大下限不相等的一个很好的例子。

假设你有一些数字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)步骤来确定它是否是素数。所以最好和最坏的情况都是一样的。
  • 假设你想排序一些 size 的数组n，并且n是 53。现在可以安排这 53 个元素，以便快速排序最终选择非常糟糕的枢轴并围绕步骤运行（最坏的情况）或非常好的枢轴并运行步骤（最好的情况）。所以最好和最坏的情况是不同的。53253 log 53
  • 现在将n上述各项设为 54：
    • 对于素数检查，只需大约1一步即可确定 54 是素数。最好和最坏的情况再次相同，但它们与 53 的情况不同。
    • 对于快速排序，您将再次遇到最坏的环绕步骤和最佳环绕步骤的情况。54254 log 54

因此，对于快速排序，最坏的情况总是围绕步骤进行，而最好的情况总是围绕步骤进行。所以最坏情况的下限和上限（或“紧”）是，最好情况的紧限是。n2n log nΘ(n2)Θ(n log n)

对于我们的主要检查，有时最坏的情况需要大约sqrt(n)步骤，有时需要大约1步骤。因此，最坏情况的下限为Ω(1)，上限为O(sqrt(n))。最好的情况也是如此。

请注意，上面我只是说“算法将是Ω(1)和O(sqrt(n))”。这有点模棱两可，因为不清楚算法是否总是为某些输入大小花费相同的时间，或者该语句指的是最好、平均或最坏的情况之一。

我该如何计算？

很难为此提供一般性建议，因为边界证明很大程度上取决于算法。您需要分析类似于我上面所做的算法以找出最坏和最好的情况。

于 2013-03-07T17:05:18.480 回答
1

Big O 和 Big Omega 可以为每种算法计算，如Big-oh vs big-theta中所见

于 2013-03-07T16:23:30.020 回答