时间复杂度问题

2015/07/07 11:04
阅读数 13

推导“大O阶”的步骤:

               1、用常数 1 取代运行时间中的所有加法常数。

               2、在修改后的运行次数函数中,只保留最高阶项。

               3、如果最高阶项存在且不是 1 ,则去除与这个项相乘的常数。

 

       下面我们在通过一个有不少 for 循环的例子按照上面给出的推导“大O阶”的方法来计算一下算法的时间复杂度。先看一下下面的这个例子的代码,也是用 C 语言写的,在注释上我们仍然对执行次数进行说明。

int n = 100000;        //执行了 1 次

               for (int i = 0; i < n; i++) {        //执行了 n + 1 次

                       for (int j = 0; j < n; j++) {        //执行了 n*(n+1) 次

                               printf("i = %d, j = %d\n", i, j);        //执行了 n*n 次

                       }

               }

               for (int i = 0; i < n; i++) {        //执行了 n + 1 次

                       printf("i = %d", i);        //执行了 n 次

               }

               printf("Done");        //执行了 1 次

 上面的代码严格的说不能称之为一个算法,毕竟它很“无聊而且莫名其妙”(毕竟算法是为了解决问题而设计的嘛),先不论这个“算法”能解决什么问题,我们看一下它的“大O阶”如何推导,还是先计算一下它的执行总次数:

 

               执行总次数 = 1 + (n + 1) + n*(n + 1) + n*n + (n + 1) + 1 = 2n^2 + 3n + 3    这里 n^2 表示 n 的 2次方。

 

       按照上面推导“大O阶”的步骤我们先来:

第一步:“用常数 1 取代运行时间中的所有加法常数”,则上面的算式变为:

 

               执行总次数 = 2n^2 + 3n + 1    这里 n^2 表示 n 的2次方

 

第二步:“在修改后的运行次数函数中,只保留最高阶项”。这里的最高阶是 n 的二次方,所以算式变为:

 

               执行总次数 = 2n^2    这里 n^2 表示 n 的2次方

 

第三步:“如果最高阶项存在且不是 1 ,则去除与这个项相乘的常数”。这里 n 的二次方不是 1 所以要去除这个项的相乘常数,算式变为:

 

               执行总次数 = n^2    这里 n^2 表示 n 的2次方

 

       因此最后我们得到上面那段代码的算法时间复杂度表示为: O( n^2 )        这里 n^2 表示 n 的2次方。

 

       至此,我们对什么是“算法的时间复杂度”和“算法的时间复杂度”表示法“大O阶”的推导方法进行了简单的说明。当然要想在日后的实际工作中快速准确的推导出各种算法的“大O阶”我们还需要进行大量的联系,毕竟熟能生巧嘛。最后我们在把常见的算法时间复杂度以及他们在效率上的高低顺序记录在这里,是大家对算法的效率有个直观的认识。

 

               O(1) 常数阶 < O(logn) 对数阶 < O(n) 线性阶 < O(nlogn) < O(n^2) 平方阶 < O(n^3) < { O(2^n) < O(n!) < O(n^n) }  

  最后三项我用大括号把他们括起来是想要告诉大家。如果日后大家设计的算法推导出的“大O阶”是大括号中的这几位,那么趁早放弃这个算法,在去研究新的算法出来吧。因为大括号中的这几位即便是在 n 的规模比较小的情况下仍然要耗费大量的时间,算法的时间复杂度大的离谱,基本上就是“不可用状态”。

本文分享 CNBlog - 削微寒的程序员之路。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

展开阅读全文
加载中
点击引领话题📣 发布并加入讨论🔥
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部