我们评估应该算法性能好坏是有俩个指标
执行时间和内存消耗
正常来说 在一个算法运行之前 我们可以预估出该算法的运行次数和运行时间
一般我们会用一种表示形态去表示上述的指标
大O表示法: O(N)
与此相关的两个概念:时间复杂度和空间复杂度
在此我们也需要了解一个概念 渐进
它表示的是:算法在输入数据的规模成倍的增长的时候 对应的时间消耗增长多少
其实大O表示法只是一种事前的估计方法,由于程序执行时间和很多因素都有关,
但是我们大部分的时候 没有必要将这些所有影响执行的时间的因素都查看一遍。
对效率来说是一种浪费,也不便于统计,
其实对于时间复杂度 只需要一个大概的结果就可以
需要强调一点:时间复杂度的计算只有输出规模大 才有意义,如果规模较小 成本上几乎可以忽略不计
常规的时间复杂度计算规则:
1.加法忽略不计就可
2.对于多项式,只保留高次幂,并且乘法系数忽略
3.对数或者含有对数乘法的因子,对数底都看做2
4.我们在估算复杂度的时候 需要输出最坏的情况,虽然最坏情况不可能发生或者
很少会发生