数据结构与算法之美 复杂度分析

Question

如何衡量编写的算法代码的执行效率呢？时间，空间复杂度分析

事后统计法，有非常大的局限性

1. 测试结果非常依赖测试环境
2. 测试结果受数据规模的影响很大

我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法

大 O 复杂度表示法

算法的执行效率，粗略地讲，就是算法代码执行的时间。

所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

$$T(n) = O(f(n))$$

T(n) 表示代码执行的时间，n 表示数据规模的大小，f(n) 表示每行代码执行的次数总和，因为这是一个公式，所以用 f(n) 表示，公式中的 O,表示代码的执行时间 T(n) 与 f(n) 表达式成正比，大 O 时间复杂度实际上不具体表示代码的真正执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫渐进时间复杂度，简称时间复杂度。

当 n 很大时，而公式中的低阶，常量，系数三部分并不左右增长趋势，所有都可以忽略，只需要记录一个最大阶的量级就可以。

时间复杂度分析

1.只关注循环执行次数最多的一段代码

这段核心代码的执行次数的 n 的量级，就是整段要分析代码的时间复杂度

2.加法法则：总复杂度等于量级最大的那段代码的复杂度

$$T1(n) = O(f(n)),T2 = O(g(n))$$

那么

$$T(n) =T1(n)+T2(n) = max( O(f(n)),O(g(n))) = O(max(f(n),g(n)))$$

3.乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

$$T(n)=T1(n)T2(n) =O(f(n)) O(g(n))= O(f(n)g(n))$$

几种常见的时间复杂度实例分析

多项式量级和非多项式量级，其中非多项式量级是 O(2n)(2 的 n 次方)，O(n!)

当数据规模 n 越来越大时，非多项式量级算法的执行时间急剧增加，求解问题的执行时间会无限增长，所以非多项式时间复杂度的算法其实是非常低效的算法。

几种常见的多项式时间复杂度

1.O(1) 只要算法中不存在循环语句，递归语句，即使有成千上万行的代码，其时间复杂度也是 O(1)
2.O(logn)O(nlogn) 在采用大 O 标记复杂度的时候可以忽略掉系数，即 O(Cf(n)) = O(f(n))
3.O(m+n) O(m*n) 代码的复杂度由两个数据的规模决定
m,n 是表示两个数据规模，所以无法事先评估 m,n 谁的量级大，所以在表示复杂度的时候，就不能简单的利用加法法则，省略掉其中一个

$$T1(m)+T2(n)=O(f(m)+f(n)) T1(m)*T2(n)=O(f(m)*f(n))$$

时间复杂度的全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系，空间复杂度全程就是渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。