定义:
一般情况下,算法中基本操作重复执行的次数是问题规模n的某个函数,用T(n)表示,若有某个辅助函数f(n),使得当n趋近于无穷大时,T(n)/f(n)的极限值为不等于零的常数,则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度,简称时间复杂度。
时间复杂度的计算:
1.先找出算法的基本操作,然后确定它的总执行次数T(n)
2.找出 T(n) 的同数量级f(n)(它的同数量级有以下:1,log2n,n,n log2n ,n的平方,n的三次方,2的n次方,n!)
3.若 T(n)/f(n) 求极限可得到一常数c,则时间复杂度T(n) = O(f(n))
例:算法:
则有 T(n) = n 的平方+n的三次方,根据上面括号里的同数量级,我们可以确定 n的三次方 为T(n)的同数量级
则有 f(n) = n的三次方,然后根据 T(n)/f(n) 求极限可得到常数c
则该算法的时间复杂度:T(n) = O(n^3) 注:n^3即是n的3次方。