外观
1.5 效率怎么量
本节问题说一种存法"快"、另一种"慢",用什么量?
最直接的想法是把程序跑一遍,看用了几秒。但同一段程序换台电脑时间就变了,换种语言也变了。秒衡量的是机器和语言,不是方法本身。要比较方法,需要一把和机器无关的尺子。
办法是不看时间,看步数:一次赋值、一次比较、读写一个格子,各算一步。步数只取决于方法和数据的规模,换台机器、换种语言都一样。
但真正关心的也不是具体几步,而是步数随着数据规模n增长,增长得有多快。n就是要处理的数据有多少:一叠试卷有n张,一行文字有n个字符,通讯录里有n个人。数据结构要处理的是几万、几百万个元素,n很小时谁快谁慢无所谓,n很大时才拉开差距。所以常数和零头都可以抹掉:不管是2步还是30步,只要不随n变化,就记作O(1),读"常数阶";不管是n步、2n步还是2n+3步,只要和n成正比,就记作O(n),读"线性阶"。这种只看趋势的写法叫大O记号,它写出来的量级叫渐进时间复杂度。第2章量线性表的每个操作时,会把这个方法用一遍。
除了O(1)和O(n),后面还会经常遇到几种量级。表里的数字是n取不同值时步数的大致规模:
| 量级 | 读法 | n=10 | n=1000 | n=1000000 |
|---|---|---|---|---|
| O(1) | 常数阶 | 1 | 1 | 1 |
| O(log n) | 对数阶 | 3 | 10 | 20 |
| O(n) | 线性阶 | 10 | 1000 | 1000000 |
| O(n log n) | 线性对数阶 | 30 | 10000 | 20000000 |
| O(n²) | 平方阶 | 100 | 1000000 | 10¹² |
注意O(log n)这一行:n从10增长到一百万,增长了十万倍,步数只从3增长到20。把一个O(n)的操作改造成O(log n),在大数据量下就是几万倍的提速——后面会看到,树这种结构之所以重要,很大程度上就是因为它能做到这一点。再看O(n²):n为一百万时步数是一万亿,普通电脑要跑很久。一个O(n²)的算法在小规模测试时感觉不到问题,数据量上去后就无法忍受。这也是为什么不能只靠"跑一下看看"来判断好坏。
空间同样可以用大O衡量,叫空间复杂度。链式存储每个元素多占几个格子记地址,n个元素就多占O(n)的空间。时间和空间之间也常常要做取舍。
到这里你有了量效率的尺子——步数随n增长的量级,以及常见的几个量级。练一练(1)从一叠打乱的试卷里找某个人的那份,最坏情况下要翻多少张?是O(1)还是O(n)?如果试卷已按学号排好呢?(2)把n个人两两握手,一共握多少次?量级是什么?(3)查字典为什么不用从第一页翻起?这对应表里哪一行?