简单的算法问题

Question

在iTunesU上观看麻省理工学院的免费算法课程，我被第一堂课吸引住了。

以插入排序为例，它的时间实际上是T(n/2)，在最坏的情况下(倒序数组/列表)，但他们说这是θn的平方。我想这应该是θn，我搞不懂他们怎么说这是n的平方。我被困在他们如何跳到这是n平方的结论，维基百科也没有帮助。有没有人能把它说得再简单一点？

Answer 1

来自wikipedia

最坏情况的输入是一个按相反顺序排序的数组。在这种情况下，在插入下一个元素之前，内部循环的每次迭代都将扫描并移位数组的整个已排序的子部分。在这种情况下，插入排序的运行时间为二次(即O(n2))。

第一个循环迭代数组/列表进行排序，内部循环迭代部分排序的数组/列表。如果它已经排序，您可以看到每次都会迭代到排序容器的末尾。

这里有更多关于伪码的解释：

for element in unsorted_container
    for current_element in sorted_container
        if element < current_element -> Will never happen since sorted in reverse order.
            InsertBefore(element, current_element)
    if element not inserted
        InsertAtEnd(element) <- Will always execute this part since it will always insert at end.

Answer 2

插入-对以相反顺序开始的4个元素的数组进行排序：

4 3 2 1

首先，将"4“插入到长度为1的数组中的适当位置(即不执行任何操作)。

接下来，将"3“插入到长度为2的数组中的适当位置：

3 4 2 1

(我们不得不移动3和4)

接下来，将"2“插入到长度为3的数组中的适当位置：

2 3 4 1

(我们必须移动2、3和4)

接下来，插入"1“

1 2 3 4

(我们必须移动1、2、3和4)

我们执行了n个步骤，每个步骤k需要移动k个元素(或k-1个交换，这取决于您如何看待它)。K从1到n的和是θ(n^2)。

在简单的链表结构*的情况下，我们可以将对象移动到O(1)中的适当位置，但通常情况下，找到适当的位置仍然需要对已经排序的数据部分进行线性搜索，因此对于一般输入，它最终仍然只有O(n^2)。但是，链表的基本插入排序恰好能很好地处理逆序数据，因为它总是能立即找到正确的插入位置。因此，对于这个特定的数据，我们得到n个步长为O(1)的步长，每个步长为O(n)。

假设我们仍然选择要插入的第一个未排序的元素，并且在每个步骤中向前搜索列表的已排序部分，那么列表的插入排序的最坏情况是已经排序的数据，并且再次是Theta(n^2)。

*意思是，没有什么比跳过列表更花哨了。