数据结构与算法1-复杂度分析1

为什么需要复杂度分析？

有两种估算方法：1.事后统计法 2.大O复杂度表示法

1. 事后统计法: 把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小

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

1. 我们需要一个不用具体的测试数据来测试，就可以粗略的估计计算法的执行效率的方法——大O复杂度表示法

   从CPU角度看，代码的执行类似这种操作：读数据——运算——写数据。

   所有代码的执行时间T(n)与每行代码的执行次数n成正比。T(n)=O(f(n)),例：T(n)=O(2n+2),T(n)=O(2n²+2n+3)

   大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫，渐进时间复杂度，简称时间复杂度。T(n) = O(n)； T(n) = O(n²)。

时间复杂度分析

1. 只关注循环执行次数最多的一段代码：核心代码执行次数的 n 的量级，就是整段要分析代码的时间复杂度
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

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

常量阶O(1) 对数阶O(logn)  线性阶O(n) 线性对数阶O(nlogn)

指数阶O(2^n)       阶乘阶O(n!)

粗略分为两类：多项式量级和非多项式量级，非多项式量级只有两个：O(2^n)和O(n!)。