O(n ^ 2)复杂度的插入排序，并对先前的值使用二进制搜索以提高复杂度 [英] Insertion Sort of O(n^2) complexity and using Binary Search on previous values to improve complexity

问题描述

如果您将算法更改为使用二进制搜索而不是搜索先前的值，直到找到插入位置，则算法的(插入代码为 O(n ^ 2))的复杂度将如何变化当前值.另外，什么时候有用?

How would the algorithm's (of Insertion Sort of O(n^2)) complexity change if you changed the algorithm to use a binary search instead of searching previous values until you found where to insert your current value. Also, When would this be useful?

推荐答案

您的新复杂度仍然是二次方的，因为您需要将所有排序的部分向右移动.因此，使用二进制搜索只会稍微好一点.

Your new complexity is still quadratic, since you need to move all of the sorted parts rightward. Therefore, using binary search is only marginally better.

对于大型数组，我建议使用快速排序算法(在 O(n log n)时间内)，二次插入排序算法仅适用于小型数组.

I would recommend a fast sorting algorithm (in O(n log n) time) for large arrays, the quadratic insertion sort algorithm is suited only for small arrays.

这篇关于O(n ^ 2)复杂度的插入排序，并对先前的值使用二进制搜索以提高复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！