算法复杂度的简单介绍
算法复杂度分为时间复杂度和空间复杂度。
最坏情况下的时间复杂度称最坏时间复杂度。一般不特别说明,讨论的时间复杂度均是最坏情况下的时间复杂度。
这样做的原因是:最坏情况下的时间复杂度是算法在任何输入实例上运行时间的上界,这就保证了算法的运行时间不会比任何更长。
常用的时间复杂度按照耗费的时间从小到大依次是:
O(C)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)
也就是说我们在设计算法时,要避免时间复杂度是n!,2^n等这样的算法。
如果复杂度是n^2,我们应下意识地去想,是否可以将复杂度降低为nlogn。
K阶多项式,只需要关注最高次幂正确即可,可以忽略所有低次幂和最高次幂的系数(n越大,最高次幂作用更明显)。