我有一个关于在插入排序算法中使用二分搜索的简单问题。更准确地说，在通常的插入排序的每一步中，我们不是将元素与前一个（已排序）子数组中的所有元素进行线性比较，而是在该已排序子数组中使用二分搜索来查找该元素所属的位置。
我知道这减少了算法进行的比较次数（O(log n) 而不是 O(n)），但每一步所需的交换次数仍然占主导地位，复杂度仍然是 O(n^2)。
我也知道复杂性与运行时间并不那么容易相关。我尝试比较两种算法对于 n（数组大小）的“小”值（最多大约 500000）的运行时间。二进制插入排序总是比通常的插入排序更快。
两者都是 O(n^2) 的事实告诉我，当 n 足够大时，运行时间应该相似，对吗？您知道在这种情况下“足够大”到什么程度才能真正看到类似的运行时间？
两者都是 O(n^2) 的事实告诉我，当 n 足够大时，运行时间应该相似，对吗？
小心——这不是真的。n^2 and 2n^2永远不会像n变大；他们的距离越来越远。但两者都是O(n^2).
那么，说你的两种算法都是意味着什么？O(n^2)？好吧，这意味着最终每个人都可以以某个恒定倍数为界n^2。对于您的二进制插入排序，它可能是10n^2，而对于您的标准插入排序，它可能是1000n^2。两者都是n^2尽管效率可能会有所不同100（在本例中）。
复杂性更多地告诉您特定函数的行为，而不是该函数如何与其他函数相比较。如果你知道你的函数是O(n^2)，例如，您知道对于较大的值n, f(n+1)将增长不超过一些常数倍n + 1（为什么？因为导数n^2 is 2n，线性，它告诉您连续项之间的差异呈线性增长）。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
