algorithm - 简单算法题

Question

在 iTunesU 上观看免费的麻省理工学院算法类(class)，我卡在了第一个类上。

以插入排序为例，在最坏的情况下(倒序数组/列表)，它的时间实际上是 T(n/2)，但他们说这是 theta n 的平方。我以为这会是 theta n。我不知道他们怎么说这是 n 平方的。我不知道他们是如何得出结论这是 n 平方的，维基百科也无济于事。有人可以进一步降低它吗？

Answer 1

对以相反顺序开始的 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的和是Theta(n^2)。

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

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

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