选择算法的运行时间为什么是O(n)？

Question

选择算法的运行时间为什么是O(n)？

50

根据Wikipedia，像快速选择这样的基于分区的选择算法具有O(n)的运行时间，但我对此持怀疑态度。有人能解释一下为什么它是O(n)吗？

在普通的快速排序中，运行时间为O(n log n)。每次我们将分支分成两个分支（大于枢轴和小于枢轴），我们需要在两个分支中继续处理，而快速选择只需要处理一个分支。我完全理解这些点。然而，如果你考虑二分搜索算法，在我们选择中间元素之后，我们也只搜索分支的一个侧面。那么这个算法是O(1)吗？不是的，当然，二分搜索算法仍然是O(log N)而不是O(1)。这也与在二叉搜索树中搜索元素相同。我们只搜索一个侧面，但我们仍然考虑O(log n)而不是O(1)。

有人能解释一下为什么在快速选择中，如果我们继续在枢轴的一个侧面搜索，它被认为是O(1)而不是O(log n)吗？我认为该算法的时间复杂度为O(n log n)，其中O(N)用于分区，O(log n)用于继续查找的次数。

- user926958

4

因为 O(N) + O(log N) = O(N)。当你做一件事然后再做另一件事时，你需要将复杂度的数量级相加，而不是相乘。 - David Schwartz

你链接的维基百科页面是关于选择算法的一般性介绍，并提到了许多这样的算法。其中一些是O(n)的，而另一些则不是；你指的是哪一个？此外，为什么要将快速排序算法与选择算法进行比较？它们有不同的目的。也许你把选择算法和选择排序混淆了？ - Antoine Gersant

这不是先做一些事情，然后再做另一些事情。如果我理解正确的话，它是每个O(logn)将O(n)划分为两个部分。 - user926958

1

@DavidSchwartz- OP的问题是，如果您需要执行O(log N)次分区步骤，每个步骤需要O(N)的时间，为什么总时间不是O(N log N)。 - templatetypedef

5个回答

20

让我试着解释一下选择排序和二分查找的区别。

每一步的操作次数在二分查找算法中都是O(1)。总共有log(N)个步骤，这使得它的时间复杂度为O(log(N))。

每一步的操作次数在选择排序算法中都是O(n)。但是这个'n'每次都会减半。总共有log(N)个步骤。因此，其时间复杂度为N + N/2 + N/4 + ... + 1 (重复log(N)次) = 2N = O(N)。

对于二分查找，操作次数是1 + 1 + ... (重复log(N)次) = O(logN)。

- Rajendran T

N + N/2 + N/4 + ... + 1 (log(N) times) 应该等于 O(NlogN)。你的 (N + N/2 + N/4 + ... + 1) 大约等于 2N，所以 2N * (logN 次方) 是 O(NlogN)。 - user926958

2

@user926958- 实际上，通过使用无限几何级数的求和公式，该总和等于2N。这就是为什么总工作量为O(N)的原因。虽然N + N + ... + N O(log N)次的总和确实是O(N log N)，但是。 - templatetypedef

“@user926958提出的问题：“N + N/2 + N/4 + ... + 1 (log(N)次方) 应该等于 O(NlogN)”是错误的，因为这是一个几何级数而不是一个等差数列。所以答案应该是大约2N。” - zhfkt

3

在快速排序中，递归树的深度为lg(N)，每个级别需要O(N)量级的工作。因此总运行时间是O(NlgN)。

在Quickselect中，递归树的深度为lg(N)，每个级别只需要比上一级少一半的工作量。这导致了以下结果：

N * (1/1 + 1/2 + 1/4 + 1/8 + ...)

或者

N * Summation(1/i^2)
    1 < i <= lgN

重要的是要注意，i的范围是从1到lgN，而不是从1到N，也不是从1到无穷大。

总和求得为2。因此，Quickselect = O(2N)。

- amrish

1

快速排序的时间复杂度不是nlogn，最坏情况下运行时间为n^2。

我猜你在问Hoare选择算法（或快速选择），而不是O(kn)的朴素选择算法。像快速排序一样，如果选择了不好的枢轴，快速选择的最坏情况运行时间为O(n^2)，而不是O(n)。正如你所指出的那样，它只对一侧进行排序，因此可以在期望时间n内运行。

- Kane

2

然而，存在某些算法（即中位数的中位数算法），它们可以在最坏情况下运行时间为O（n）。 - templatetypedef

0

因为对于选择而言，你不一定需要排序。你可以简单地计算有多少个项目具有任何给定值。因此，可以通过计算每个值出现的次数，并选择具有50％项目在其上下的值来执行O(n)中位数。这是对数组的一次遍历，仅为数组中的每个元素递增计数器，因此它是O(n)。

例如，如果您有一个8位数字数组“a”，则可以执行以下操作：

int histogram [ 256 ];
for (i = 0; i < 256; i++)
{
    histogram [ i ] = 0;
}
for (i = 0; i < numItems; i++)
{
    histogram [ a [ i ] ]++;
}
i = 0;
sum = 0;
while (sum < (numItems / 2))
{
    sum += histogram [ i ];
    i++;
}

最后，“i”变量将包含中位数的8位值。这大约需要通过数组“a”进行1.5次遍历。一次完整地遍历数组以计算值，再半途返回以获取最终值。

- user1118321

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

有几种不同的选择算法，从简单得多的快速选择（预期O(n)，最坏情况O(n²)）到更为复杂的中位数算法（Θ(n)）。这两个算法都通过使用快速排序分区步骤（时间O(n)）来重新排列元素并将一个元素定位到其正确位置。如果该元素在所询问的索引处，则我们完成了并可以返回该元素。否则，我们确定要递归的哪一侧并在那里递归。

现在让我们做出一个非常强的假设-假设我们使用快速选择（随机选择枢轴），并且在每次迭代中我们都能够猜出数组的确切中间位置。在这种情况下，我们的算法将按如下方式工作：我们执行分区步骤，丢弃数组的一半，然后递归地处理数组的一半。这意味着在每个递归调用上，我们最终会执行与该级别处的数组长度成比例的工作量，但是该长度在每次迭代时都会减少一半。如果我们计算出数学公式（忽略常数因子等），我们最终得到以下时间：

第一级别的工作量：n
进行一次递归调用后的工作量：n / 2
进行两次递归调用后的工作量：n / 4
进行三次递归调用后的工作量：n / 8
...

这意味着总工作量由以下公式给出：

n + n / 2 + n / 4 + n / 8 + n / 16 + ... = n (1 + 1/2 + 1/4 + 1/8 + ...)

请注意，最后一个项是1、1/2、1/4、1/8等的总和乘以n。如果您计算此无限和，尽管有无限多个项，但总和正好为2。这意味着总工作量为：

n + n / 2 + n / 4 + n / 8 + n / 16 + ... = n (1 + 1/2 + 1/4 + 1/8 + ...) = 2n

这可能看起来很奇怪，但是想法是如果我们在每个级别上进行线性工作，但将数组分成两半，那么我们最终只需要做大约2n的工作。

这里有一个重要的细节，即确实有O(log n)个不同的迭代，但并不是所有迭代都做相等数量的工作。事实上，每次迭代做的工作量是前一次迭代的一半。如果忽略工作正在减少的事实，则可以得出工作量为O(n log n)，这是正确但不是紧密的界限。使用工作量在每次迭代上持续下降的事实进行更精确的分析，可以得到O(n)运行时间。

当然，这是非常乐观的假设——我们几乎永远不会得到50/50的分割！ ——但是使用更强大版本的这种分析，您可以说如果您可以保证任何常数因子的分割，则完成的总工作量仅为n的某个常数倍。如果我们在每次迭代中随机选择一个元素（如quickselect中所做的），则在期望上，我们只需要选择两个元素，然后在数组的中间50%选择某个主元素，这意味着期望只需要选择两轮主元素，然后才能选出给出25/75分割的元素。这就是quickselect的期望运行时间为O(n)的来源。
中位数算法的正式分析要困难得多，因为递归方程很棘手且不易分析。直观上看，该算法通过进行少量工作来保证选择好的主元素。但是，由于存在两个不同的递归调用，像上面那样的分析方法将无法正确地奏效。您可以使用一个称为 Akra-Bazzi定理的高级结果，或者使用大O符号的正式定义明确证明运行时间为O(n)。有关更详细的分析，请参阅Cormen、Leisserson、Rivest和Stein的《算法导论第三版》。