1.3 归纳总结与思维拓展

教材导航 · 第1章

原书定位

印刷页P11起,对应PDF第23页。下文为目视整理的知识提要;完整内容见原书对照。

复杂度分析先选基本操作,再把执行次数与规模建立关系;循环变量参与条件时可列不等式,递归算法则建立递推式。

  • i←2ii\leftarrow2i:执行次数为 Θ(log⁡n)\Theta(\log n)。
  • 累加 1+2+⋯+t1+2+\cdots+t 达到 nn:t=Θ(n)t=\Theta(\sqrt n)。
  • T(n)=T(n−1)+O(1)T(n)=T(n-1)+O(1):O(n)O(n);T(n)=T(n/2)+O(1)T(n)=T(n/2)+O(1):O(log⁡n)O(\log n)。
  • 斐波那契朴素双递归反复计算子问题,时间为指数级,调用栈 O(n)O(n);迭代保存相邻两项,时间 O(n)O(n)、额外空间 O(1)O(1)。

关联知识

原书对照

展开原书对照截图

原书对照,原书P11,PDF第23页