算法复杂度

简介

　　同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

时间复杂度

时间频度

　　一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。算法的时间复杂度是指执行算法所需要的计算工作量。

时间复杂度

　　一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),存在一个正常数c使得fn*c>=T(n)恒成立。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

　　当随着n越来越大时，常数项、低次项可以被忽略，例如T(n) = n2+2n+3 ,O(f(n) =  n2， 如果n的次方是平方，系数也可以忽略，例如5n2 = n2

常见的时间复杂度

1. 常数阶O(1),对数阶O(log2n)(以2为底n的对数，下同),线性阶O(n)
2. 线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3)
3. k次方阶O(n^k),指数阶O(2^n)

由小到大依次为：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜ Ο(nk) ＜Ο(2n) 

空间复杂度

算法复杂度

原文：https://www.cnblogs.com/ftlzypx/p/15111467.html