Skip to content
第2章

2.7 顺序表的时间复杂度 ​

时间复杂度看什么 ​

本节问题
编辑器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)。

选中正文里的任意文字,就可以针对它发表评论