1.大O表示法
1.1 算法时间度量指标
- 算法实施的操作数量或步骤数可以作为独立于具体程序或机器的度量指标
- 赋值语句是一个合适作为度量的选择
1.2 问题规模影响算法执行时间
- 问题规模：影响算法执行时间的主要因素
- 算法分析的目标：找出问题规模如何影响算法执行时间
1.3 数量级函数
- 基本操作数量函数
T(n)的精确值并不是特别重要，重要的是T(n)中起决定性因素的主导部分 - 数量级函数描述了
T(n)中随着n增加而增加速度最快的主导部分，称为大O表示法，记作O(f(n))，其中f(n)表示T(n)中的主导部分，即T(n)中变化最快的部分
1.4 影响算法执行的其他因素
某些具体数据也会影响算法运行时间
- 分为最好、平均、最差情况，平均情况体现了算法的主流性能
- 对算法分析看主流
1.5 常见的大O数量级函数
1.6 其他算法复杂度表示方法
- 大O表示法：表示了所有上限中最小的那个上限
- 大Ω表示法：表示了所有下限中最大的那个下限
- 大θ表示法：上下限相同时可以使用大θ表示
2.“变位词”判断问题
2.1 问题描述
- 问题描述：所谓变位词是指两个词之间存在组成字母的重新排列关系，例如：
heart和earth。为了简单起见，假设参与判断的两个词仅由小写字母构成，而且长度相等。 - 解题目标：写一个
bool函数，以两个词作为参数，返回这两个词是否为变位词 - 意义：展示同一问题的不同数量级算法算法
2.2 解决方案
2.2.1 逐字检查
思路：将词1的字符逐个到词2中检查是否存在，存在就打勾。如果每个字符都能找到，则说明两个词的变位词；如果存在一个词找不到，则不是变位词。
问题规模：词中包含字符个数n
主要部分在于两重循环，总执行次数为
$$
\frac{n(n+1)}{2}\rightarrow O(n^2)
$$
2.2.2 排序比较
思路：将两个字符串按照字母顺序排列，再逐个比较字符，如果相同则是变位词，如果不同则不是变位词
本算法的主要执行时间在排序步骤，运行时间数量级等于排序过程的数量级
O(nlogn)
2.2.3 暴力法
- 思路：穷尽所有可能组合，检查是否存在
- 本算法的主要执行时间数量级为
O(n!)
2.2.4 计数比较
- 思路：记录各字母出现的次数，如果相同则说明是变位词
- 本算法的主要执行时间数量级为
O(n)
3.Python数据类型的性能
3.1 list和dict各种操作的大O数量级
3.1.1 列表list
- 最常用的是：按索引取值和赋值，均为O(1)
- 另一个常用的是列表增长，可以选择
append()或者+，执行复杂度分别为O(1)和O(n+k) pop()的时间复杂度为O(1)，pop(i)的时间复杂度为O(n)
使用timeit模块进行计时，其中可以指定反复运行次数
3.1.2 字典dict
- 最常用的取值
get和赋值set，其性能为O(1) - 另一个重要操作
contains(in)，其心梗也是O(1)