算法的时间复杂度

算法的时间复杂度
    分析一个算法的好坏，时间复杂度是一个非常重要的标准。我们一般用O()表示一个算法的复杂度。
　　常见的算法时间复杂度有（由小到大）：
　　
O(1)常数阶   O(logn)对数阶   O(n)线性阶   O(nlogn)   O(n^2)   O(n^3) 
| --------             p问题（时间复杂度为上）               -----------|

O(2^n)    O(n!)
|-NP问题(复杂度为上)-|

    计算时间复杂度可分为递归和非递归两种：

　　举一个简单的例子：计算斐波拉契数列  f (n) = f (n-1) +f (n-2)   (n  <  45)
    有些人第一眼看到这个问题，觉得用递归十分方便，便毫不犹豫的用了递归（这是某大学的一个考研题，很多人采用了这种算法，但是当他们将程序提交上去，在规定时间内都未能给出答案，他们都觉得不知所云），其实当我们计算过时间复杂度后，出现这个问题的原因就一目了然了。

    如果我们采用递归的方式，那么我们设进入一次递归（一个基本操作）程序运行的时间为一个单位时间
故计算       T (n) = T (n-1) + T (n-2)  + 1
       变形  T (n) + 1 = T (n-1)  + 1 + T (n-2)  + 1
       令    B (n) = T (n)+1
       所以  B (n) = B (n-1) + B (n-2)
       可见 B (n) 也是一个斐波拉契数列
       所以时间复杂度 T (n) = B (n) -1 = f (n)
    当n = 45 时，斐波拉契数列的值在 2,100,000,000 ,这意味着当我们计算斐波拉契的第45项时，我们要执行21亿次基本操作，这是不可想象的！！！因为在递归的过程中执行了大量的无用的重复计算！！！

    如果我们采用非递归的方法递推的话，十分简单，时间复杂度为 O (n)

    我在这里并不是说递归的时间复杂度一定比非递归的时间复杂度高，而是说明对于同一个问题，有不同的算法去解决这个问题，我们在之前一定要分析算法的时间复杂度。否则我们写的程序对时间的开销是不可估量的。而我们在写递归的时候，要特别注意里面嵌套了多个递归的情况。