2.11 链表的时间复杂度

先回顾方法

2.6节回顾过方法：不看秒，看步数；不看具体几步，看步数随n增长的趋势；抹掉常数和零头，只留量级，得到渐进时间复杂度，用大O记号表示。

量顺序表时，关键是数"挪动了多少个元素"。量链表，关键是数"顺着next走了多少步"——每走一步读一次next，就是一步基本操作。设表长为n，逐个看。

逐个操作

Init造一个头结点，Length读一个计数器，都是固定几步，O(1)。

Get(L, i)的全部工作在NodeAt里：从头结点出发走i+1步。i最小是0，走1步；i最大是n−1，走n步。最坏O(n)，平均走n/2步，也是O(n)。这是链表和顺序表差别最大的地方：顺序表Get是一次加法算出地址，O(1)；链表没有地址可算，只能一站一站走。

Locate从第0个结点开始逐个比较，最坏比较n次，O(n)。和顺序表一样。

Insert(L, i, x)分两段。第一段NodeAt(L, i−1)，走i步找到前一个结点，最坏O(n)；第二段造结点、改两个地址，固定几步，O(1)。加起来是O(n)。Delete同理，定位O(n)，越过并释放O(1)，合计O(n)。

Destroy要释放每一个结点，O(n)。

和顺序表放在一起

操作	顺序表	链表
Init、Length	O(1)	O(1)
Get	O(1)	O(n)
Insert、Delete	O(n)	O(n)
Locate	O(n)	O(n)

Insert和Delete两边都是O(n)，但慢的原因不同，这一点要看清楚。顺序表定位是O(1)，慢在挪动后面的元素；链表不挪动任何元素，改地址只要O(1)，慢在定位——要从头走到第i−1个。也就是说，链表的插入删除本身是O(1)，前提是已经站在前一个结点上。如果不需要从头走，链表就赢了；如果每次都要从头走，链表并没有比顺序表好。

Get则是链表单方面吃亏：顺序表O(1)，链表O(n)。这是"相邻格子放相邻元素"这条约定换来的好处，放弃约定就一并放弃了。

回到编辑器

现在可以回答上一节的问题了：编辑器2.0快没快？

看它怎么用链表。光标cursor是一个整数，敲一个字符调用Insert(&text, cursor, ch)，Insert里的NodeAt要从头结点走cursor步找到前一个结点，然后改两个地址。光标在行首，走0步，快；光标在行尾，走n步，慢。

和顺序表比一下：顺序表是行尾快、行首慢，链表是行首快、行尾慢——正好反过来，但都是O(n)。换了链表，只是把慢的位置从一头搬到了另一头，问题并没有解决。

还有一处更糟。Show每显示一次，要从0到n−1逐个调用Get，而链表的Get每次都从头走：取第0个走1步，取第1个走2步……取第n−1个走n步，加起来约n²/2步，O(n²)。顺序表的Show是n次O(1)的Get，O(n)。编辑器每处理一条指令都要Show一次，换成链表之后，显示反而慢了一个量级。

问题出在哪？链表的优势是"站在前一个结点上时，插入删除O(1)"，而编辑器的光标是一个整数，每次都要重新从头走到那个位置，优势完全没用上。光标本来就一直停在编辑的位置，为什么不让它直接记住那个结点，而要记一个数字再从头找？这就是下一节要做的事。