谁的程序更厉害？——时间复杂度浅谈
|
381
|
算法
|
tdiant

怎么看谁的程序更厉害呢？

如果我让两个人为了解决同一个问题，写了两个不一样的程序，但是这两个程序都能办成同一件事，我应该选择谁的程序呢？

也就是说，我们需要一种东西，这种东西能衡量两个不同的程序谁更厉害。
解决这个问题最重要的问题就是，评判的标准是什么。

我们卡啥标准好呢？

程序在运行的时候消耗的最重要的两个硬件，一个是CPU，一个是内存。也就是程序算了多少次、占了多大内存空间，对于一个程序而言非常重要。

因此，要是评判两个程序谁更厉害，最起码应该看两个程序用时多少，内存占了多少。

怎么卡时间呢？

程序占了多少内存是显而易见的，打开任务管理器这之类的工具一看就看到了。那程序执行一次用了多少时间怎么看？

解决一个实际问题的思路

不妨带入一个实际的问题中来看一看。

问题：编写一个程序，求1到100的所有整数和，并输出。

如果要是学了循环，这个问题很简单，大致应该这样写：

#include<iostream>
using namespace std;
int main(){
    int sum = 0, i = 1;
    for(;i<=100;i++){
        sum += i;
    }
    cout << sum;
    return 0;
}

工作原理很简单。我整了一个int类型的变量sum，初始值给了0。
现在我开了一个for循环，为此我又定义了一个变量叫做i。很明显，根据for循环的功能，i会依次等于1、2、3……一直到100，并且每次变化的时候都会给sum加i，达到从1加到100的目的。

然而有些人不这么想。他们在小学二年级就听说了高斯发明了一种算法，很轻松就能把这个题算出来了，也就是等差数列求和。写的话只需要算一算(100+1)*100/2即可，也就是（首项+尾项）*项数/2。

他写了这样的程序：

#include<iostream>
using namespace std;
int main(){
    int sum = (100+1) * 100 / 2;
    cout<<sum;
    return 0;
}

好了，现在两个程序都能解决同一个问题，谁更优秀呢？

比一比谁用的时间更短？

有的人说了，害，没关系，我想个方法看看两个程序从运行到输出结果用了多少时间不就好了？
然后他发现，第一个程序跑完用的时间可能大约是5ms，第二个程序可能是1ms，显然第二个用的时间比第一个用的时间更短，第二个程序更厉害。

但是，我现在想说，这样比较程序运行时间来衡量算法厉不厉害的方法根本不可取。

假如我把上面第二个程序发给了张三说，看我写的这个程序，贼厉害，1ms就把1到100的和就算完了，而我隔壁的老王写的程序得用5ms才能跑完，我是不是很厉害啊。
张三在他电脑上跑了一下，发现在他电脑上跑的用时是5ms，他可能会不屑一顾，啊？就这？你的程序跟老王写的差不了多少呀，有啥大不了的。

问题出在哪里呢？每个人电脑配置不一样啊。比如同样一个1+1，他的电脑可能算几天几页，我的电脑可能一眨眼就出来结果了，电脑一直更新换代，算的速度也越来越快啊。
如果要是用这种方式在计算机界衡量两个算法，那肯定就乱套了。

所以显然，有很多因素直接影响着程序的运行时间快慢，程序的运行时间没法更好的描述这个算法究竟厉不厉害了。

来看看新评判标准——时间复杂度

什么是时间复杂度？

程序运行的快慢居然没办法用程序的运行时间来衡量了。我们需要一种新的评判方式来衡量程序谁快谁慢。
隆重向您介绍时间复杂度。我们可以比较两个程序的时间复杂度来比较两个程序的快慢。

我们认为数据的规模设一个数字叫做n，从1到100求和这件事规模大概就是100了，认为n=100。
那么，在n相同的情况下，两个程序表现如何呢？

对于一个电脑而言，他的计算速度很快，虽然肯定有差异，但是我们可以直接认为1+1和345*567这两个式子算起来对于CPU而言时间都差不多一样。就是说，两个计算步骤用的时间基本上可以认定为都一样。
那既然如此，答案很明显：一个程序究竟算了多少次式子，直接决定着程序的用时。
时间复杂度正是代表着这个计算次数，所以时间复杂度可以完美的衡量程序的快慢。

那时间复杂度咋玩呢？

我们按刚才那个题的两个程序来说明。
第一个程序在n这个范围下，for循环导致计算的步骤数量恰好是n，所以时间复杂度我们用这样的写法来记录：O(n)。
第二个程序在n这个范围下，他只算了一步，很显然，这个程序的时间复杂度是O(1)。

一些小规则

参数可忽略

那么再来看看这个程序时间复杂度是多少：

#include<iostream>
using namespace std;
int main(){
    int sum = 0, i;
    for(i = 1; i < 100; i++){
        sum += i;
        sum += i;
    }
    cout<<sum;
    return 0;
}

他这个程序不得了，数据范围如果是n，一个for循环里面有两个加法计算。也就是一次循环进行了两次计算，按照刚才的思路，时间复杂度是O（2n）。

但是，实际上时间复杂度是一个“渐进的复杂度标记方式”。你可以认为时间复杂度是这样的一个函数，他描述着数据范围是自变量，时间是因变量的函数，我们评判程序优略只需要看变化的趋势就行了。因此，2这个常量不会影响y=x这个函数的变化趋势，没什么用，我们干脆就不写了，直接认为这个算法的时间复杂度也是O(n)。

仅要最大次项

限于篇幅，不再举例。

如果存在一个程序，时间复杂度最后计算出来是O(n²+n)，我们可以直接把n这一项扔掉，因为n²这一项是影响增长趋势的关键项，其他的项都没啥用，干脆就不写了，所以这个算法时间复杂度是O(n²)

常见的复杂度比较

一般我们有这些常见的时间复杂度形式，按照用的时间从少到多，大致可以这样排序：

O(1 )< O(logn) < O(n) < O(n*logn) < O(n^2) < O(n^3) < O(2^n) < O(n!) < O(n^n)

在书写对数的时候，logn就是指真数是10时n的对数。说白了就是lgn。
那么这是咋弄出来的呢？这个程序的复杂度刚好符合O(logn)，注意i是怎么变的。

int main(){
    int i = 1;
    int n = 100;
    while(i<n)
        i *= 2;
    return 0;
}

以后写程序要注意的事情

现在我说完了评判算法优劣的两个重要标准，一个是时间复杂度，一个是空间复杂度。
上面的程序中，同样是解决1到100的和的问题，第一个程序显然没有第二个程序更好。写程序应该不只是为了解决问题，而是追求写的更好才可以。

那么你可能会问，刚才那个问题的最优解就是第二个程序了呗？不对，最优解是这个，哈哈：

#include<iostream>
using namespace std;
int main(){
    cout << 5050;
    return 0;
}
上一篇
下一篇