统计代码复杂度的2种方法
1、事后统计法
通过统计，监控 得到算法执行的时间和占用的内存大小。
局限性：测试结果依赖测试环境，受数据规模的影响很大，
2、大O复杂度表示法
有没有什么方法可以避免事后统计法的弊端，不需要具体的测试数据和环境，就可以粗略的估算算法的执行效率。
有，俗称 大O复杂度表示法，我觉得也可以叫事前估算法
算法的执行效率：简单来说就是算法代码执行的时间
所有代码的执行时间T(n) 与每行代码的执行次数n成正比
T(n) = O(f(n))
T(n) 代码执行时间
O 表示代码执行时间T(n)与f(n)表达式成正比
大O时间复杂度表示法，不代表代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势
所以也叫 渐进时间复杂度，简称时间复杂度
如何进行时间复杂度分析
1、只关注循环执行次数最多的一段代码
2、加法法则：总复杂度等于量级最大的那段代码的复杂度
3、乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的积
常见时间复杂度及分析
多项式量级
1、常量阶 O(1)
2、对数阶 O(logn)
3、线性阶 O(n)
4、线性对数阶 O(nlogn)
5、平方阶 O(n2) 立方阶O(n3) K次方阶 O(kn)
非多项式量级
1、指数阶 O(2N)
2、阶乘阶 O(n!)
随数据量的增加，执行时间会急剧增加 算是一种非常低效的算法
O(1) 常量级时间复杂度的一种表示方法，不代表只执行了一行代码
即代码执行时间不随数据量的增大而增长，这样的代码时间复杂度都记为O(1)
一般情况下，只要算法中不存在循环语句，递归语句，即使有成千上万行代码，时间复杂度也是O(1)
O(logn) O(nlogn)
对数阶
很常见的时间复杂度，也是最难分析的一种时间复杂度。
i = 1;
while(i<=n){
i = i*2;
}
只需计算 第3行代码执行的次数
2x = n
x = log2n 以2为底N的对数
空间复杂度 全称 渐进空间复杂度
表示算法的存储空间与数据规模之间的增长关系
常见空间复杂度 O(1) O(n) O(n2)
像O(logn) O(nlogN)这样的对数阶复杂度平时都用不到
空间复杂度要比时间复杂度分析简单的多
小结
复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率和数据规模之间的增长关系。可以粗略的表示，越高阶复杂度的算法，执行效率越低。
常见的复杂度不多，从低阶到高阶有： O(1) O(logn) O(n) O(nlogn),O(n2)
几乎所有的数据结构和算法的复杂度都跑不出这几个
几个概念：
最好情况时间复杂度（理想情况下，执行代码的时间复杂度）概率低
最坏情况时间复杂度（糟糕情况下，执行代码的时间复杂度）概率低
平均情况时间复杂度
均摊时间复杂度
解决不同情况下算法复杂度的问题，只有同一块代码在不同的情况下， 时间复杂度有量级的差距，才会使用这三种复杂度表示法来区分
网友评论