这里告诉你如何计算算法的时间复杂度（大O阶）

前言

该文章已经进行了一次排版的优化。

关于时间复杂度

在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。这是一个代表算法输入值的字符串的长度的函数。时间复杂度常用大O符号表述，不包括这个函数的低阶项和首项系数。使用这种方式时，时间复杂度可被称为是渐近的，亦即考察输入值大小趋近无穷时的情况。例如，如果一个算法对于任何大小为 n （必须比n0大）的输入，它至多需要5n3 + 3n的时间运行完毕，那么它的渐近时间复杂度是O(n3)。源自:wikipedia

为了计算时间复杂度，我们通常会估计算法的操作单元数量，每个单元运行的时间都是相同的。因此，总运行时间和算法的操作单元数量最多相差一个常量系数。
Step：

1. 用常数1替代语句频度中所有的加法项；
2. 在1 的结果中，只保留数的最高项；
3. 最高阶项若系数不为1，则去除系数（或是改为1）。

如果你没看懂，那继续往下看，笔者以例子与你详细介绍。
例子1

for(int sum=0,i = 0;i < N;i++)  //1、
    for(int j = 0;j <N;j++)     //2、
        sum=sum+i*j;           //3、

我们以一个语句记为1次，来：

1. 1行这里定义两个变量共一次，而中间循环，理论是判断是N次,但是实际上应该是N+1，最后等于N时还有判断1次 即0~N，故为N+1，循环变量的递增一共是N次，其语句频度为:
   $$O_1=1+(N+1)+N\text{\hspace{1em}(1.1)}$$

2. 2行这里第一个循环进入第二个循环，一共是N次，那么将会定义N次。单独分析判断语句它将会像第一层循环一样，一个判断N次，再算上第一次循环进入第二次循环共有N次， 故为N * (N+1)，后面类似N*N，其语句频度为:
   $$O_2=N+N\ast (N+1)+N\ast N\text{\hspace{1em}(1.2)}$$

3. 第二层循环进入最里面语句N次，第一层循环进入第二层循环共N次，故实际为N * N次。其语句频度为:
   $$O_3=N\ast N\text{\hspace{1em}(1.3)}$$

4. 那么将上述的（1.1）、（1.2）、（1.3） 式子求和一下，就得这个程序的总的语句频次，并保留最高项数N * N，就得到了该程序的算法时间复杂度。
   $$O(N^2)=O_1+O_2+O_3\text{\hspace{1em}(1.4)}$$

例子2

int j = 0;
for(int sum = 0,i = 1;i < N;i = i*2)   //1、
        sum = sum+i*j;             //2、

看到这程序片段，你是不是一眼就得出答案了？如果你不注意的话，你的答案肯定是O(N)，对了吗？
先告诉你答案为O(log(N)) 不是这个答案的，你可以试试代个确切的N值进去 看一下次数,自己体会一下，那么下面我和大家一起分析下：

1. 注释1的语句频度为：
   $$O_1=1+lo{g}_{2}N+1+lo{g}_{2}N\text{\hspace{1em}(2.1)}$$

2. 注释2的语句频度为：
   $$O2=lo{g}_{2}N\text{\hspace{1em}(2.2)}$$

3. 总的算法时间复杂度为：
   $$O(lo{g}_{2}N)=O_1+O_2\text{\hspace{1em}(2.3)}$$

其实这里做判断的时候，应该看一下循环变量的递增方式，这里它是i=i*2 也就是 2^x=N，那么X=log2(N),x就是次数，在计算复杂度里面，一般省略底数，也就是直接写log(N),其他的计算方法与上面的解释一致。

例子3

for(int sum=0,i = 0;i<N;i++)        //1、
    for(int j = 1;j < N;j = j*2)     //2、
        sum=sum+i*j;                //3、

答案分析:

1. 注释1的语句频度为：
   $$O_1=1+N+1+N\text{\hspace{1em}(3.1)}$$

2. 注释2的语句频度为：
   $$O_2=N+N\ast (lo{g}_{2}N+1)+N\ast lo{g}_{2}N\text{\hspace{1em}(3.2)}$$

3. 注释3的语句频度为：
   $$O_3=N\ast lo{g}_{2}N\text{\hspace{1em}(3.3)}$$

4. 总的算法时间复杂度为：
   $$O(N\ast lo{g}_{2}N)=O_1+O_2+O_3$$

如果你认真仔细地边看边思考，那么我相信你应该是能够理解如何去计算时间复杂度了，那么任何程序相信在你们自己的简单化下，应该都能分出它们的大致大O阶。
那么，关于算法的时间复杂度就描述到这里。谢谢你的浏览，如果你喜欢的话，记得点个赞。

欢迎前往我的个人博客,该文章已同步至我的个人博客: 遇见山人