2.6 顺序表的时间复杂度

编辑器跑起来了。一行只有几十个字符，每个操作都是瞬间完成，快慢感觉不出来。但如果把这个结构用在几万字的文档上会怎样？这需要用第1章的尺子来量。

先回顾一下这把尺子。衡量算法快慢不用秒，用步数，而且真正关心的不是具体几步，而是步数随着n的增长，增长得有多快。步数不随n变化的，记作O(1)；步数和n成正比的，记作O(n)；和n²成正比的，记作O(n²)。至于是n步、2n步还是2n+3步，常数和零头一律抹掉，只留量级。因为只看n很大时的趋势，这种分析方法叫渐进时间复杂度分析，大O记号写出来的就是渐进时间复杂度。

用这个方法量顺序表，关键是数"挪动了多少个元素"——每挪一个元素是一步基本操作。设表长为n，逐个看六个操作。

Init、Length、Get都是固定几步，与n无关，O(1)。Get之所以快，就是"补充：地址与指针"里看到的那件事：数组连续，第i个元素的地址一次算出。

Insert的步数取决于挪动多少个元素。在位置i插入，要挪动第i个到第n−1个，共n−i个。i=n时（末尾追加）挪0个，最好情况O(1)；i=0时（行首插入）挪n个，最坏情况O(n)。各位置机会均等时平均挪n/2个，仍是O(n)。

Delete同理，删第i个要挪n−i−1个，最坏和平均都是O(n)。

Locate最坏要比较n次，O(n)。

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

放回编辑器看：光标在行尾打字，每个字符都是追加，O(1)，很快；光标在行首打字，每敲一个字符都要把整行往后挪一遍，O(n)。几万字的文档，在开头打字就会明显卡顿。

这个问题的根源是顺序存储"相邻格子放相邻元素"的约定本身——只要坚持这个约定，中间插入就必然要挪动。在顺序表的框架内没有办法，要换一种存储方式才能解决，这是2.8节的内容。在此之前，先解决一个更急迫的问题。