Question

个人理解时间复杂度.请大神看看理解有问题不

我理解的情况是T(n)是根据问题规模而增长的时间复杂度,是一个准确的时间,但是呢.因为是预先对程序的时间进行判断,所以不会计算的那么的准确,就需要一个接近的时间值,也就是个大概的时间来表示这个程序的时间复杂度T(n),
时间复杂度T(n)和基本操作的执行次数函数f(n)是成正比的,如果基本操作执行1次,时间是2秒
那么执行2次就是4秒
而O(f(n))就是渐进时间复杂度.渐进时间复杂度我理解的意思是接近时间复杂度T(n).
O(f(n))是怎么计算的呢
他是根据执行次数中增长率最快的那一项来计算的,比如在n(n+1)/2这个执行次数来说
把(n(n+1))/2拆开来就是(n^2+n)/2中间.当n扩大时,n^2增长比n快.所以只要计算n^2的时间就可以算出这个程序的时间复杂度,只能说是一个接近值.并不是一个准确的值
所以公式T(n) = O(f(n))也可说T(n)约等于O(f(n))
求大神看看理解上是否有错误,还是根本没理解对呢?

Answer 1

理解正确，也可以与高数的同阶无穷大联系起来，当n趋近于无穷大时，一般来说，T(n)也是无穷大量，如果n趋近于无穷大时，T(n)/f(n)的极限趋近于常数，则T(n)与f(n)是同阶无穷大，记作T(n)=O(f(n)),也可以说f(n)是T(n)的渐近时间复杂度。

追问

T(n)/f(n)的极限趋近于常数是什么意思呢。能具体点吗？f(n)是T(n)的数量级又是什么意思。谢谢帮忙

追答

　　例如：
　　for(i=1; ii; j--)
　　if(a[j]无穷大][n(n-1)/2]/n^2=lim[n--->无穷大][(1-1/n)/2]=1/2 (常数)
　　T(n)与n^2是同阶无穷大， 即T(n)=O(n^2)