复杂度分析（上）

如何分析、统计算法的执行效率和资源消耗

数据结构和算法解决的是快 和 省的问题
复杂度分析是整个算法学习的精髓，只要掌握了他数据结构和算法的内容基本就掌握了一半。
这里有个词叫“庖丁解牛”

为什么要进行：
直接统计算法的运行时间：事后统计法 有非常大的局限性

1、测试结果非常依赖测试环境
不同的机器，不同的cpu结果不近相同，有时候还会有截然相反的情况
2、测试结果受数据量的影响很大
例如排序，待排序数组的有序度不一样，排序的执行时间就会有很大的差别。
对于小规模的数据排序，插入排序反倒会比快速排序要快

所以我们需要一个不用具体测试数据就能粗略估计算法的执行效率
这就是今天说的内容。

大O复杂度表示法

算法执行效率，粗略的讲 就是算法代码执行的时间，如何在不执行代码的情况下用肉眼得到一段代码运行的时间

从CPU的角度来看，每段代码的每一行都执行者 读数据 - 运算 - 写数据 ；尽管每行代码对应的CPU执行个数、执行时间都不一样，但是粗略估算每行代码执行的时间都是一样的 为一个定值。

大O来了：大O时间复杂度表示法 如下
T（n） = O（f（n））

这种表示法实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随着数据规模增长的变化趋势。所以也叫做 --> 渐进时间复杂度 简称时间复杂度

这个当 n 很大时 可以想像成10000 、 100000000 ，而公式中的低阶、常量、系数必不能左右增长趋势，所以忽略。

时间复杂度分析

1、只关注循环执行次数最多的一行代码，我们在分析一个算法、一段代码的时间复杂度的时候，也只关注循环次数最多的那一段代码就可以了。，这段代码执行次数的n的量级，就是整段分析代码的时间复杂度
2、加法法则：总复杂度等于量级最大的那段代码的复杂度
3、乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

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

常量级别
对数
线性
线性对数
平方 立方 n次方
指数
阶乘

以上可以分为两类
多项式量级
非多项式量级： 指数 和 阶乘 两个

当n越来越大的时候 非多项式量级执行时间急剧增加，求解问题的时间无限加长