二、算法分析¶
什么是算法分析¶
程序和算法的区别¶
- 算法是对问题解决的分步描述
- 程序则是采用某种编程语言实现的算法。
同一个算法，通过不同编程语言的不同编写方式，可以产生很多程序。
算法分析的概念¶
算法分析，主要是从计算资源消耗的角度，来评判和比较算法。
能够更高效利用计算资源，或者更少占用计算资源的算法，就是好算法。
计算资源指标¶
什么是计算资源呢？
一种是算法解决问题过程中，需要的存储空间或内存¶
存储空间收到问题自身数据规模的变化影响，要区分哪些存储空间是问题本身描述所需，哪些是算法占用，并不容易。
另一种是算法的执行时间¶
可以通过对程序进行实际运行测试，获得真实的运行时间
Tips
- python 的 time 模块，在算法开始、结束时，分别记录系统时间，求其差值即可获得运行时间。
- 最好能多次运算，求均值。
运行时间检测的分析¶
程序运行的实际时间，会受到不同编程语言及实际运行环境差异的影响。因此，需要用更好的方法来衡量算法运行时间。
而这个指标，需要与具体的机器、程序、运行时段都无关。
大O表示法¶
算法时间度量指标¶
一个算法所实施的操作数量，或者步骤数可以作为独立于具体程序/机器的度量指标。
赋值语句 同时包含了（表达式）计算和（变量）存储两个基本资源。
Tips
其实，除了与计算资源无关的定义语句外，主要就是三种控制流语句和赋值语句，而控制流仅仅起了组织语句的作用，并不实施处理。
赋值语句执行次数¶
无
问题规模影响算法执行时间¶
问题规模——影响算法执行时间的主要因素。
算法分析的目标——找出问题规模会怎样影响一个算法的执行时间。
数量级函数 Order of Magnitude¶
T(n)的精确值并不是特别重要，重要的是T(n)中起决定性因素的主导部分
数量级函数，描述了 T(n) 中随着 n 增加而增加速度最快的主导部分。
Note
称作大O表示法，记作 O(f(n))， 其中 f(n) 表示 T(n) 中的主导部分。
确定运行时间数量级大O的方法¶
无
影响算法运行时间的其他因素¶
- 有时候，决定运行时间的不仅是问题规模，某些具体数据也会影响算法运行时间
- 分为最好、最差、和平均情况，平均状况体现了算法的主流性能
常见的大O数量级函数¶
- 当 n 较小时，难以确定其数量级
- 当 n 增到较大时，容易看出其主要变化量级
Tips
共有七种主要的大O数量级函数
| f(n) | 名称 |
|---|---|
| 1 | 常数 |
| log(n) | 对数 |
| n | 线性 |
| n*log(n) | 对数线性 |
| n^2 | 平方 |
| n^3 | 立方 |
| 2^n | 指数 |
其他算法复杂度表示法¶
- 大O表示法：所有上限中，最小的那个上限。
- 大欧米茄表示法：所有下限中，最大的那个下限。
- 大希尔塔表示法：如果上下限相同，可用此表示法。
变位词判断问题（上）¶
变位词判断问题¶
问题描述¶
所谓“变位词”是指两个词之间存在组成字母的重新排列关系。如 heart 和 earth。