use*_*958 29 algorithm big-o selection
根据维基百科,选择算法具有运行时间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)继续寻找的次数.
tem*_*def 69
有几种不同的选择算法,从更简单的快速选择(预期的O(n),最坏情况的O(n 2))到更复杂的中位数中值算法(Θ(n)).这两种算法都通过使用快速分配步骤(时间O(n))来重新排列元素并将一个元素定位到其适当位置.如果该元素位于相关索引处,我们就完成了,并且可以返回该元素.否则,我们确定在哪一侧进行递归并递归.
现在让我们做一个非常强大的假设 - 假设我们使用quickselect(随机选择枢轴),并且在每次迭代时我们设法猜测数组的确切中间位置.在这种情况下,我们的算法将如下工作:我们执行分区步骤,丢弃一半数组,然后递归处理数组的一半.这意味着在每次递归调用时,我们最终会在该级别上与数组的长度成比例地工作,但是该长度在每次迭代时保持减少两倍.如果我们计算出数学(忽略常数因子等),我们最终得到以下时间:
这意味着完成的总工作量由下式给出
n + n/2 + n/4 + n/8 + n/16 + ... = n(1 + 1/2 + 1/4 + 1/8 + ...)
请注意,这最后一个项是n,1/2,1/4,1/8等之和的n倍.如果计算出这个无穷大的总和,尽管存在无限多个项,但总和是这意味着总工作量是
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%中选择一些pivot元素,这意味着,在期望,在我们最终选择能够进行25/75分割的东西之前,只需要两轮选择一个支点.这是quickselect的O(n)的预期运行时间来自.
对中位数算法的正式分析要困难得多,因为复发很困难且不易分析.直观地,该算法通过做少量工作来保证选择好的枢轴.但是,因为有两个不同的递归调用,所以像上面这样的分析将无法正常工作.您可以使用称为Akra-Bazzi定理的高级结果,也可以使用big-O的形式定义来明确证明运行时为O(n).有关更详细的分析,请查看Cormen,Leisserson,Rivest和Stein的"算法简介,第三版".
希望这可以帮助!
Raj*_*n T 11
让我试着解释选择和二元搜索之间的区别.
每个步骤中的二进制搜索算法都进行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)