一般情况下,算法的基本操作重复执行的次数是模块n的某一个函数f(n),因此,算法的时间复杂度记做:T(n)=O(f(n)),一般人认为,T(n)是f(n)中增长最快的项/此项的系数. 比方说T(n) = 2n^5 + 3n^2 - 1 为 O(T(n) = O(2n^5/2) = O(n^5) 其实这是错误的计算方法, 真正意义上的时间复杂度而是数学中极限的概念.

   还是上面的例子,可以用下面的公式去转换:

   \lim_{n\to\infty}\frac{T(n)} {\ xf(n)}= 常数 (其中x为项系数)), 假如左边等式成立,则f(n)为T(n)的时间复杂度.什么意思呢?

   我们用上面的例子来看下:

   \lim_{n\to\infty}\frac{T(n)} {\ xf(n)}= lim_{n\to\infty}\frac{2n^5 + 3n^2 - 1}{\ 2n^5}   = 常数

   所以这个T(n)的时间复杂度为O(n^5), 再举个通俗例子:

   比如求 n^k 和k^n的时间复杂度的比较, 其中(k为常数,k>1,且k属于正整数), 如果按照之前的错误求法是很难求的, 试试极限的思想:

   \lim_{n\to\infty}\frac{n^k} {\ k^n}=lim_{n\to\infty}\frac{log_2(n^k)}{\ log_2(k^n)} =lim_{n\to\infty}\frac{klog_2(n)}{\ nlog_2k} = 0

   因为n\to\infty, 很简单的就可以通过极限求出来了,结果为: O(n^k)要远远好于O(k^n) .

   顺便来说一下程序片段的时间复杂度,如下面的程序:

void fun (int n) {
    int i = 1;
    while (i <= n) {
        i = i*2;
    }
}

   上面这个程序可以看出 int i = 1;为O(1)的, 这里是求基本运算语句i = i*2 ,我们这里直接设它执行y次,则:

   2^y*i = n 这里的i可以省略,不影响时间复杂度的计算, 所以y = log_2n => O(log_2n). 就说到这, 有问题请交流:)