第14话:如何计算算法的时间复杂度

大O记法的实践
服务器君一共花费了340.749 ms进行了6次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

算法的时间复杂度定义为:

在进行算法分析时,语句总的执行次数T(n)是关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间量度,记作:T(n}=0(f(n))。它表示随问题规模n的增大,算法执行时间的埔长率和 f(n)的埔长率相同,称作算法的渐近时间复杂度,简称为时间复杂度。其中f( n)是问题规横n的某个函数。

  • 这样用大写O()来体现算法时间复杂度的记法,我们称之为大O记法。一般情况下,随着n的增大,T(n)增长最慢的算法为最优算法。
  • 之前我们说的三个求和算法的时间复杂度分别为0(n),0(1),0(n2)。我就推一下吧。

计算 1 + 2 + 3 + 4 + ...... + 100。代码如下,之前也有讲过:

#include "stdio.h"

int main()
{
    int i, sum = 0, n = 100;	/* 执行1次 */
    for( i = 1; i <= n; i++)	/* 执行 n+1 次 */
    {
        sum = sum + i;			/* 执行n次 */
        //printf("%d \n", sum);
    }
    printf("%d", sum);			/* 执行1次 */
}

从代码附加的注释可以看到所有代码都执行了多少次。那么这写代码语句执行次数的总和就可以理解为是该算法计算出结果所需要的时间。该算法所用的时间(算法语句执行的总次数)为: 1 + ( n + 1 ) + n + 1 = 2n + 3

而当 n 不断增大,比如我们这次所要计算的不是 1 + 2 + 3 + 4 + ...... + 100 = ? 而是 1 + 2 + 3 + 4 + ...... + n = ?其中 n 是一个十分大的数字,那么由此可见,上述算法的执行总次数(所需时间)会随着 n 的增大而增加,但是在 for 循环以外的语句并不受 n 的规模影响(永远都只执行一次)。所以我们可以将上述算法的执行总次数简单的记做: 2n 或者简记 n

这样我们就得到了我们设计的算法的时间复杂度,我们把它记作: O(n)

再来看看高斯的算法:

#include "stdio.h"

int main()
{
    int sum = 0, n = 100;	/* 执行1次 */
    sum = (1 + n) * n/2;	/* 执行1次 */

    printf("%d", sum);		/* 执行1次 */
}

这个算法的时间复杂度: O(3),但一般记作 O(1)。

从感官上我们就不难看出,从算法的效率上看,O(3) < O(n) 的,所以高斯的算法更快,更优秀。

下面再来一个例子:

#include "stdio.h"

int main()
{
    int i, j, x = 0, sum = 0, n = 100;	/* 执行1次 */
    for( i = 1; i <= n; i++)
    {
        sum = sum + i;
        //printf("%d \n", sum);
        for( j = 1; j <= n; j++)
        {
            x++;                /* 执行n*n次 */
            sum = sum + x;
        }
    }
    printf("%d", sum);			/* 执行1次 */
}

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

执行总次数 = 1 + (n + 1) + n*(n + 1) + n*n + (n + 1) + 1 = 2n2 + 3n + 3

如何推导大o阶呢?我们给出了下面 的推导方法:

  1. 用常数1取代运行时间中的所有加法常数。
  2. 在修改后的运行次数函数中,只保留最髙阶项。
  3. 如果最高阶项存在且不是1,则去除与这个项相乘的常数。

按照上面推导“大O阶”的步骤我们先来第一步:“用常数 1 取代运行时间中的所有加法常数”,则上面的算式变为:执行总次数 = 2n^2 + 3n + 1

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

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

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

  • 最后我们在把常见的算法时间复杂度以及他们在效率上的高低顺序记录在这里,是大家对算法的效率有个直观的认识。

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

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

延伸阅读

此文章所在专题列表如下:

  1. 第一话:你的数据结构怎么学的?
  2. 第二话:数据结构的历史与来由
  3. 第三话:关于数据结构的一些概念
  4. 第四话:数据的逻辑结构
  5. 第五话:数据的物理结构
  6. 第六话:关于数据类型
  7. 第七话:抽象数据类型ADT
  8. 第八话:补充数据结构基本概念的关系
  9. 第九话:数据结构与算法的关系
  10. 第10话:什么是算法?
  11. 第11话:算法的五个基本特征
  12. 第12话:什么样的算法才是好算法
  13. 第13话:算法的性能分析
  14. 第14话:如何计算算法的时间复杂度
  15. 第15话:算法的最坏情况与平均情况
  16. 第16话:算法的空间复杂度

本文地址:http://www.nowamagic.net/librarys/veda/detail/2195,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2195

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

大家都在看

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《代码之美》 聂雪军 (译者)

《代码之美》介绍了人类在一个奋斗领域中的创造性和灵活性:计算机系统的开发领域。在每章中的漂亮代码都是来自独特解决方案的发现,而这种发现是来源于作者超越既定边界的远见卓识,并且识别出被多数人忽视的需求以及找出令人叹为观止的问题解决方案。《代码之美》33章,有38位作者,每位作者贡献一章。每位作者都将自己心目中对于“美丽的代码”的认识浓缩在一章当中,张力十足。38位大牛,每个人对代码之美都有自己独特的认识,现在一览无余的放在一起,对于热爱程序的每个人都不啻一场盛宴。 虽然《代码之美》的涉猎范围很广,但也只能代表一小部分在这个软件开发这个最令人兴奋领域所发生的事情。

更多计算机宝库...