一些数学基础

首先我们需要明确一些数学概念，具体的定义我就不说了，个人觉得最重要的就是函数的典型的增长率，这里从上到下增长率逐渐增加：

为了直观的查看，简单画了一下函数的图，函数的公式也贴出来了，如果想更进一步查看，请自行用python验证。

基本操作次数

做几个比喻：

场景一：有一条10寸的面包，每3天吃掉1寸，那么吃完这个面包需要几天？

答案： 3x10=30天

如果是N寸呢？那么自然是3xN = 3N天。

如果用一个函数表示这个相对时间，那么就是T(N) = 3N

场景二：有一条16寸的面包，每5天吃掉剩余长度的一半，第一次8寸，第二次4寸，第三次2寸，那么吃得只剩1寸，需要几天。

翻译一下就是数字16不停的除以2,要除多少个2还为1。2^x=16, x = lg16/lg2, 这里记为log16。所以我们需要log16次，所以需要5xlog16 = 5x4 = 20天。

所以当面包长为N时，那么我们需要T(N)=5log(N)。

场景三：有一条长为10寸的面包和一个鸡腿，每两天吃掉一个鸡腿，吃掉整个鸡腿需要几天？

答案自然是2天。因为只吃掉鸡腿，和面包没有关系。

如果面包长度是N呢？

无论面包有多长，吃掉鸡腿的时间仍为2天，记作T(n)=2。

场景四：有一条长10寸的面包，吃掉第一个一寸的需要的时间是1天，吃掉第二个一寸需要2天，吃掉第三个一寸需要3天......也就是说每多吃一寸，所花的时间也多一天。那么吃掉整个面包需要多少天？

答案是1累加到10的总和，55天。

如果面包的长度是N寸呢？

此时吃掉整个面包需要，1+2+3+......+n-1+n = (1+n)*n/2(等差数列公式)。

记作 T(N) = 0.5N^2 + 0.5N

上面所讲的是吃东西所花费的相对时间，这一思想同样适用于对程序基本操作次数的统计。

所以分别对应的函数如下：

场景一：T(n) = 3n, 执行次数是线性的。

#include <iostream>using std::cout;using std::endl;void eat1(int n){    for(int i = 1; i <= n; ++i){        cout << "Day" << 3*i-2 <<" 等待一天" << endl;        cout << "Day" << 3*i-1 <<" 等待一天" << endl;        cout << "Day" << 3*i-0 <<" 吃掉面包, 还剩"<< n-i <<"寸"<< endl;    }}int main(){    eat1(5);}

场景2： T(n) = 5logn，执行次数是对数的。

#include <iostream>using std::cout;using std::endl;void eat2(int n){    for(int i = 1, j = 1; i < n; i*=2, j++){        int k = 5*j - 4;        cout << "Day" << k+0 <<" 等待一天" << endl;        cout << "Day" << k+1 <<" 等待一天" << endl;        cout << "Day" << k+2 <<" 等待一天" << endl;        cout << "Day" << k+3 <<" 等待一天" << endl;        cout << "Day" << k+4 <<" 吃掉一半面包，还剩" << n/(i+1) <<"寸"<< endl;    }}int main(){    eat2(8);    return 0;}

场景3： T(n) = 2, 执行次数是常量的。

#include <iostream>using std::cout;using std::endl;void eat3(int n){    cout << "Day" << 1 <<" 等待一天" << endl;    cout << "Day" << 2 <<" 吃掉一个鸡腿"<< endl;}int main(){    eat3(8);    return 0;}

场景4：T(n) = 0.5n^2 + 0.5n, 执行次数是一个多项式

#include <iostream>using std::cout;using std::endl;void eat4(int n){    int count = 0;    for(int i = 1; i <= n; ++i){        for(int j = 1; j < i; ++j){            ++count;            cout << "Day" << count <<" 等待一天" << endl;        }        ++count;        cout << "Day" << count <<" 吃掉面包, 还剩"<< n-i <<"寸"<< endl;    }}int main(){    eat4(5);}

渐进时间复杂度

有了基本操作次数的函数T(n)，是否就可以分析和比较一段代码的运行时间了呢？还是有一定的困难。比如算法A的相对时间是T(n)=100n，算法B的相对时间是T(n) = 5n^2，这两个到底谁的运行时间更长一些？这就要看n的取值了。所以这时候有了渐进时间复杂度的概念。官方的定义如下：若存在函数f(n)，使得当n趋近于无穷大时，T(n)/f(n)的极限值为不等于于零的常数，则f(n)是T(n)的同数量级函数。

记作T(n) = O((f(n))，称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。

渐进时间复杂度用大O来表示，所以成为大O表示法。

如何推导出时间复杂度呢？有如下规则：如果运行时间是常数量级，用常数1表示；只保留时间函数中的最高次项；如果最高阶存在，则省去最高阶项前面的系数。

所以我们回头看前面4个场景的时候，我们会得到：

场景一：T(n)=3n=O(n) -- 最高阶项为3n，省去系数3。

场景二：T(n)=5logn = O(logn) - 最高阶项为5logn，省去系数5。

场景三：T(n)=2=O(1) - 常数量级

场景四：T(n)=0.5n^2+0.5n = O(n^2) - 最高阶项为0.5n^2,省去系数0.5

那么这四种时间复杂度谁用时更长，设节省时间呢？为了更直观的找到答案，这里我画了这4个数量级的函数图像，函数越大，表明更耗时，时间复杂度就更大。

O(1) < O(logN) < O(n) < O(n^2)

当然还有如我在文章一开始提到的其他复杂度。

时间复杂度的巨大差异

也许有些人会问，这年头计算机性能越来越强大，我们为什么还要花时间耗在时间复杂度上呢？

这里举一个例子吧。

算法A的相对时间规模是T（n）= 100n，时间复杂度是O(n)

算法B的相对时间规模是T（n）= 5n^2，时间复杂度是O(n^2)

算法A运行在老旧电脑上，算法B运行在某台超级计算机上，运行速度是老旧电脑的100倍。

那么，随着输入规模 n 的增长，两种算法谁运行更快呢？

从上面的表格中我们可以看到，当n很小时，算法A的运行用时远大于B，当n的到达1000时，算法A和算法的运行时间已经接近；当n的值越来越大，达到十万、百万时，算法A的优势开始显现，就算慢100倍又如何，还是比你算的快。这就是不同时间复杂度带来的差距，这里多说一句，当前是信息爆炸的时代，海量的数据，更要求我们关注时间复杂度的优化，况且你还有一台比前人性能优越了不知多少倍的计算机，想象一下一辆宝马却和一台拖拉机一个速度，说出去我都觉得不好意思！！！