Skip to content
第1章

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=10n=1000n=1000000
O(1)常数阶111
O(log n)对数阶31020
O(n)线性阶1010001000000
O(n log n)线性对数阶301000020000000
O(n²)平方阶100100000010¹²

注意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)查字典为什么不用从第一页翻起?这对应表里哪一行?
选中正文里的任意文字,就可以针对它发表评论