二进制插入排序和复杂度 [英] Binary insertion sort and complexity

问题描述

我有一个关于在插入排序算法中使用二进制搜索的简单问题.更准确地说，在常规插入排序的每个步骤中，我们没有线性比较该元素与先前(排序的)子数组中的所有元素，而是仅在该排序的子数组中使用二进制搜索来查找该元素所属的位置.

I have a simple question about using binary search in the insertion sort algorithm. More precisely, at each step of the usual insertion sort, instead of linearly comparing the element with all the elements in the previous (sorted) subarray, we just use binary search in that sorted subarray to find the place where the element belongs.

我知道这减少了算法进行的比较次数(O(log n)而不是O(n))，但是每一步所需的交换次数仍然占主导地位，复杂度仍然为O(n ^2).

I know that this reduced the number of comparisons that the algorithm makes (O(log n) instead of O(n)), but the number of swaps needed at each step still dominates and the complexity is still O(n^2).

我也知道，复杂度与运行时间并不那么容易.我试图比较两种算法的n值(数组大小)的小"值(最多约500000)的运行时间.二进制插入排序总是比通常的插入排序快.

I also know that complexity is not so easily related to running time. I have tried to compare the running time for both algorithms for "small" values of n (array size), up to about 500000. Binary insertion sort was always faster than usual insertion sort.

两个都是O(n ^ 2)的事实告诉我，当n足够大时，运行时间应该相似，对吗?在这种情况下，有多少足够大"才能真正看到相似的运行时间的想法?

The fact that both are O(n^2) tells me that as n gets large enough, the running time should be similar, right? Any idea on what "large enough" would be in this situation to actually see similar running times?

推荐答案

两个都是O(n ^ 2)的事实告诉我，当n足够大时，运行时间应该类似，对吧?

The fact that both are O(n^2) tells me that as n gets large enough, the running time should be similar, right?

小心-事实并非如此.随着 n 变大， n ^ 2 和 2n ^ 2 永远不会靠近.他们分开得更远.但是两者都是 O(n ^ 2).

Careful - this isn't true. n^2 and 2n^2 will never get closer together as n gets bigger; they get farther apart. But both are O(n^2).

那么，说您的两个算法都是 O(n ^ 2)是什么意思?好吧，这意味着最终每个人都可以被 n ^ 2 的某个恒定倍数所限制.对于您的二进制插入排序，它可能是 10n ^ 2 ，而对于您的标准插入排序，它可能是 1000n ^ 2 .两者均为 n ^ 2 ，尽管效率可能相差 100 (在此示例中).

What does it mean, then, to say that both your algorithms are O(n^2)? Well, it means that eventually each one can be bounded above by some constant multiple of n^2. For your binary insertion sort, it might be 10n^2, whereas for your standard insertion sort it might be 1000n^2. Both are n^2 though the efficiency may differ by a factor of 100 (in this example).

复杂性不仅可以告诉您某个特定函数的行为，还可以告诉您该函数与其他函数的堆叠方式.例如，如果您知道函数是 O(n ^ 2)，则知道对于 n 的大值， f(n + 1) n + 1 会以不超过某个常数倍的速度增长(为什么?因为 n ^ 2 的导数是 2n ，线性，这告诉您连续项之间的差异呈线性增长).

Complexity tells you more about a particular function's behavior than it does about how that function stacks up against others. If you know your function is O(n^2), for instance, you know that for large values of n, f(n+1) will be grow by no more than some constant times n + 1 (why? because the derivative of n^2 is 2n, linear, which tells you that the difference between consecutive terms grows linearly).

这篇关于二进制插入排序和复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！