时间复杂度
时间复杂性
T = T(N,I)
N为规模，
I为输入
元运算Oi的次数ei每次运算的时间t1..tkT(N,I) = sum(1..k) ti*ki时间复杂度记作T(n)=Of(n)
算法效率与f(n)成正比
渐进分析符号
__mindmap__topic
- f(n)=O(g(n))-> a<=b
- f(n)=Ω(g(n))-> a>=b
- f(n)=Θ(g(n))-> a=b
- f(n)=o(g(n))-> a<b
- f(n)=w(g(n))-> a>b
最常用的关系式
1.多项式：a0+a1n+…+adn^d =Θ n^d
多项式中，只取最大项为该式的时间复杂度
2.对数：O(Log)a n = O(log)b n
无论两个对数的底是什么常数，两对数的时间复杂度相等
3.对数：任意x>0, log n = O(n^x )
对数时间复杂度一定小于次方时间复杂度
4.指数：任意r>0,d>0, n^d = O(r^n)
次方时间复杂度一定低于指数时间复杂度