时间复杂度看什么
本节问题编辑器1.0在几十个字符上,每个动作都是瞬间完成。拿它编辑一个几万字的文档,哪个动作会变慢?能不能不靠运行,看代码就判断出来?
时间复杂度描述的是:当输入规模n增大时,算法执行的基本操作次数随n增长的趋势。对顺序表来说,n就是表长。
它不关心具体跑了多少毫秒,那取决于机器、语言和编译器;它只关心量级,所以用大O记号表示,忽略常数和低阶项。比如某算法执行3n²+5n+2次操作,就记作O(n²)。操作次数不随n变化,记作O(1)。
下面用这个方法,把顺序表的五个操作逐个量一遍。
初始化。Init只做一件事:把length设成0。不管表里原来有3个字符还是3万个,都只有这一步。操作次数不随n变化,所以Init是O(1)。
求长度。Length只做一件事:返回length。长度早就记在length里,不用一个一个去数。同样只有一步,所以Length是O(1)。
取第i个元素。表的字符放在一段连续的格子里,比如从100号开始:
text ┌───┬───┬───┬───┬───┐
… │ c │ a │ t │ │ │ …
└───┴───┴───┴───┴───┘
100 101 102 103 104
第0个字符在100号,第1个在101号,第i个就在100+i号。要取第i个,直接就能找到它所在的格子,不用从头一个一个数过去。不管n多大,都只要固定几步,所以Get是O(1)。
插入和删除的时间复杂度
插入要走多少步?开头的检查、最后放入元素和长度加1,都是固定的几步。插入的步数主要花在挪动元素上:每挪一个元素,就是一步赋值。所以步数有多少,取决于要挪几个元素,也就取决于插在哪里。
text ┌───┬───┬───┬───┬───┐
data │ c │ a │ t │ │ │ length = 3
└───┴───┴───┴───┴───┘
0 1 2 3 4
可以插在尾部、头部,或者中间的某个位置。逐个看。
尾部插入。在行尾追加s,就是Insert(3, 's')。s直接放进第3个格子,一个元素都不用挪,只走固定的几步:
text ┌───┬───┬───┬───┬───┐
data │ c │ a │ t │ s │ │ length = 4
└───┴───┴───┴───┴───┘
0 1 2 3 4
表长换成1万、10万,尾部插入还是这几步。步数不随n变化,所以尾部插入是O(1)。
头部插入。在行首插入b,就是Insert(0, 'b')。为了把第0个格子腾出来,t、a、c都要往后挪一格:
text ┌───┬───┬───┬───┬───┐
data │ c │ a │ t │ │ │ length = 3
└───┴───┴───┴───┴───┘
0 1 2 3 4
└──►└──►└──►
挪完之后,b放进第0个格子:
text ┌───┬───┬───┬───┬───┐
data │ b │ c │ a │ t │ │ length = 4
└───┴───┴───┴───┴───┘
0 1 2 3 4
表长为n时,头部插入要把n个元素全挪一遍,步数是n再加上固定的几步。n是3就要挪3次,n是1万就挪1万次,n是10万就挪10万次。步数和n成正比,所以头部插入是O(n)。
中间插入。插在中间的第i个位置。比如在第1个位置插入x,就是Insert(1, 'x'),a和t要往后挪,挪2次:
text ┌───┬───┬───┬───┬───┐
data │ c │ a │ t │ │ │ length = 3
└───┴───┴───┴───┴───┘
0 1 2 3 4
└──►└──►
一般地,在第i个位置插入,要挪第i个到第n−1个元素,一共挪n−i次。i越靠前,步数越多。如果每个位置被插入的机会一样,平均挪n/2次。忽略常数1/2,还是O(n)。
插入的三种情况:
| 插入的位置 | 时间复杂度 |
|---|
| 尾部 | O(1) |
| 头部 | O(n) |
| 中间第i个 | O(n) |
尾部是最好的情况,头部是最坏的情况,中间位置平均下来也是O(n)。说一个操作的时间复杂度,通常看最坏的情况,所以Insert是O(n)。
删除。删除的步数同样主要花在挪动元素上,只是方向相反:删掉一个元素之后,它后面的元素要往前挪,把空出来的格子补上。也分三种情况。
删尾部的元素,后面没有元素要挪,只走固定的几步,是O(1)。
删头部的元素,后面n−1个元素都要往前挪一格,步数和n成正比,是O(n)。
删中间的第i个,要把第i+1个到第n−1个往前挪,一共挪n−i−1次,平均下来也和n成正比,是O(n)。
删除的三种情况:
| 删除的位置 | 时间复杂度 |
|---|
| 尾部 | O(1) |
| 头部 | O(n) |
| 中间第i个 | O(n) |
和插入一样看最坏的情况,Delete是O(n)。
顺序表五个操作的时间复杂度汇总如下:
| 操作 | 顺序表 |
|---|
| Init、Length、Get | O(1) |
| Insert、Delete | O(n) |
编辑器各条指令的时间复杂度
编辑器的每条指令,都是用顺序表的五个操作做的。上一页已经有了每个操作的时间复杂度,这里逐条套用。设这一行有n个字符。
敲字符:i c。调用Insert(L, cursor, c)。光标在行尾是尾部插入,O(1);在行首是头部插入,O(n);在中间也是O(n)。所以敲字符是O(n)。
退格:d。调用Delete(L, cursor−1),删的是光标左边那个字符。光标在行尾是尾部删除,O(1);光标越靠前,后面要往前挪的字符越多,最坏是O(n)。所以退格是O(n)。
左移、右移:l和r。只改cursor,右移前再调用一次Length看是不是到了行尾。都是固定几步,O(1)。
显示。Show调用一次Length和n次Get,每次都是O(1),合起来是O(n)。
这是本书为了程序简单,每条指令之后都打印整行。真正的编辑器只重画屏幕上看得见的那几十个字符,所以显示不是要解决的问题。
回到开头的问题。拿编辑器1.0编辑几万字的文档,慢的是在开头附近敲字符和退格:每按一下,光标右边的几万个字符都要挪一遍。
这个问题的根源,是顺序存储"相邻的元素放在相邻的格子里"这条约定本身。只要坚持这条约定,在中间插入就必然要挪动。在顺序表的框架里没有办法,要换一种存储方式才能解决,这是2.9节的内容。
在那之前,编辑器1.0还有一个更急的问题要先解决。