时间复杂度的计算

本文讲的仅仅是一个大致的概念，如果需要更深入的了解，还是要查阅算法书籍的。（写本文的目的是为了给一个同学讲清楚）

算法的效率评价通过算法时间复杂度和空间复杂度来描述，本文中我主要讲的是时间复杂度。时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？嗯，是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个工具！（我是这么理解的）。还有，一个算法所花费的时间与其中语句的执行次数成正比例，这就意味着，我们的计算与这些语句有关。

我们可以记住一句话，“算法中的基本操作的执行次数，为算法的时间复杂度”。那么，什么是基本操作呢：基本操作就是算法中的每一条语句，我们通常可以只考虑循环内的语句就行了（最内层循环里的语句哦）。

OK，在我们的程序中，我们总能找到一个n，这个n是问题的规模，比如循环的次数，数组或者链表结构元素的个数等，而我们的时间复杂度就是关于这个问题规模n的函数T(n)，T(n)实际上叫做“渐进时间复杂度”简称为时间复杂度。现在了解了什么是时间复杂度，可是还是不会计算，所以，我们再引进一个函数f(n)。还记得刚刚一直在提的“基本操作的执行次数”吗：f(n)就是这个执行次数。

现在，我们要把T和f联系起来了：T(n)=O(f(n))。O是数量级的符号。一般而言呢，我们取f(n)中随n增大增长最快的项，然后将该项的系数变为1。

举个例子来说：f(n)=3n⁴+2n²+1，那么T(n)=O(f(n))=O(n⁴)。

再来回顾一下：算T(n)=>找出基本操作，确定问题的规模n=>计算基本操作执行次数f(n)=>得出T(n)

来看一个栗子吧^^

1 void test(int n){
2     int i = 0;
3     int j = 0;
4     while(i < n)
5     {
6         i+=2;
7         j++;
8     }
9 }

例1

上面是一段很简单的代码，那么它的时间复杂度是多少呢？

解：

基本操作是：6,7两行的代码（至于2,3两行的代码也可以算上，但是一般而言，取循环内的就足够了，其实取一行就够了），那么哪一个变量影响最终基本操作的执行次数呢，其实就是while语句的执行次数，也就是这里传进来的n的大小，晓得了这个之后，就可以计算f(n)了。

f(n)是基本操作的执行次数，这里我们仅仅取第6行作为基本操作（取两行仅仅是系数上的变化，不影响最终结果）。则：

2*f(n)+M=n（M是一个常量，用来校准结果）

可以得到f(n)=(n-M)/2。

所以：T(n)=O(f(n))=O(n/2-M/2)=O(n)。

下面，要讲一些规则：

加法规则：

T(n,m) = O(max(f(n),g(m)) 说白了就是取最大的那个

乘法规则：

T(n,m) = O(f(n)*g(m))

T(n,m) = O(f(n)*C) = O(f(n)) C是一个常量

这些规则可以方便我们计算更复杂的程序。

例1的函数，除了循环换里面的内容外，其他的语句复杂度都是O(1)，了解了上面的规则之后，可以明白为什么不计算他们了吧？

了解时间复杂度的好处是？...（“应付考试！”哈，很多同学会这么想）改进算法！

比如有一个程序是这样：

1 void sum(int n)
2 {
3     int sum = 1;
4     for(int i = 0; i < n; i++){
5         sum = sum + i;
6     }
7     cout<<sum<<endl;
8 }

例2

这一段代码是计算sum = 1 + 2 + 3 + ... + n

时间复杂度为O(n)

我们可以利用sum = 1 + 2 + 3 + ... + n = n*(n+1)/2 来设计程序

1 void sum(int n)
2 {
3     int sum = 1;
4     sum = n * ( n + 1 ) / 2
5     cout<<sum<<endl;
6 }

时间复杂度立刻变为了O(1)，算法的效率提高了很多了吧！

再来举一个例子：

1 void test(int n)
2 {
3     int i = 1;
4     while(i <= n )
5     {
6         i = i*2;
7     }
8 }

例3

基本的执行语句是第6行，执行了f(n)次，也就是说2^f(n)+M=n忽略掉M，f(n)=log₂n故而T(n)=O(log₂n)

最后，给出一个常见时间复杂度的大小顺序：

O(1)≤O(log₂n)≤O(n)≤O(nlog₂n)≤O(n²)≤O(n³)≤...≤O(n^k)≤O(2ⁿ)

注：在大O表示法中，任何非0正常数都属于同一数量级，记为O(1)。

（本文网址：http://www.cnblogs.com/marsdu/p/3178989.html）

文中若有错的地方，欢迎大家指出，但不接受任何喷子。

时间复杂度的计算

推荐阅读