我是算法新手，对它很着迷。
Hi I am new to algorithms and am quite fascinated by it.
我试图弄清楚插入排序的最坏情况下的时间复杂度，它被称为O （n ** 2）。相反，我们可以将时间复杂度设为O（N * logN）。
I am trying to figure out worst case time complexity of insertion sort and it is mentioned as O(n**2). Instead, we can have the time complexity as O(N*logN).
这是我的解释，
插入排序将查看第一个元素，并假定它已排序。接下来，它查看第二个元素，并与1个元素的先前排序子列表进行比较，并根据与先前排序子列表中的元素进行比较将其插入。
THe insertion sort looks at the 1st element and assumes it is sorted. Next it looks at the 2nd element and compares with the predecessor sorted sublist of 1 element and inserts it based on the comparison with elements in the predecessor sorted sublist. This process is repeated similarly.
到处都提到要在前一个排序的子列表中插入元素，基本上是线性搜索，这需要O（N）时间，因此已经对n个元素执行了这些操作，需要我们O（N ** 2）。
Everywhere it is mentioned that to insert an element into the predecessor sorted sublist, basically linear search,it takes O(N) time and as we have do these operations for n elements it takes us O(N**2).
但是，如果我们使用二进制插入将元素插入到先前的子列表中，则应该O（logn）时间，其中n是子列表的长度。基本上将新元素与先前排序的子列表的中间元素进行比较，如果它大于中间元素，则新元素位于子列表的中间元素和最后一个元素之间。
However, if we use binary insertion to insert the element into predecessor sublist it should take O(logn) time where n is the length of sublist. Basically compare the new element with the middle element of predecessor sorted sublist and if it is greater than the middle element then new element lies between the middle element and the last element of the sublist.
当我们重复n个项目的运算时，应该使我们成为O（N * logN）。我们可以使用二进制搜索方法，因为我们知道前一个子列表已排序。
As we repeat the operations for n items it should take us O(N*logN). We can use binary search approach as we know the predecessor sublist is sorted.
因此，最坏情况下的时间复杂度不应该是O（N * logN）而不是O（ N ** 2）。
So shouldn't the worst case time complexity be O(N*logN) instead of O(N**2).
推荐答案是的，您可以在O（log n）中找到插入点，但是为插入项目留出空间。这需要O（n）时间。
Yes, you can find the insertion point in O(log n), but then you have to make space to insert the item. That takes O(n) time.
请考虑以下部分排序的数组：
Consider this partially-sorted array:
[1,2,3,5,6,7,9,4]您到达最后一项4，然后进行二进制搜索以找到需要插入的位置。但是现在您必须腾出空间，这意味着将项目9、7、6和5向下移动到数组中的一个位置。这就是使插入排序为O（n ^ 2）的原因。
You get to the last item, 4, and you do a binary search to locate the position where it needs to be inserted. But now you have to make space, which means moving items 9, 7, 6, and 5 down one place in the array. That's what makes insertion sort O(n^2).