第13话:算法的性能分析

如何判断一个算法的效率
服务器君一共花费了133.858 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

算法的设计要注意效率,这里效率大都指算法的执行时间。一个用高级程序语言编写的程序在计算机上运行时所消耗的时间取决于下列因素:

  1. 算法采用的策略、方法。
  2. 编译产生的代码质量。
  3. 问题的输入规模。
  4. 机器执行指令的速度
  • 第1条当然是箅法好坏的根本,第2条要由软件来支持,第4条要看硬件性能。也就是说,抛开这些与计算机硬件、软件有关的因素,一个程序的运行时间,依赖于算法的好坏和问题的输入规模。所谓问题输入规模是指输入量的多少。

比如计算从1加到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次 */
}

上面是最常见的算法,再来看一下小时候高斯的算法

#include "stdio.h"

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

    printf("%d", sum);		/* 执行1次 */
}
  • 正如程序的注释中计数一样,第一种算法,执行了 1+ (n+1) +n+l次=2n+3次;而第二种算法,是 1+1+1=3次。
  • 事实上两个算法的第一条和最后一条语句是一样的,所以我们关注的代码其实是中间的那部分,我们把循环看作一个整体,忽略头尾循环判断的开销,那么这两个算法其实就是n次与1次的差距。算法好坏显而易见。

再来看一个程序:

#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次 */
}
  • 这个例子中,i从1到100,每次都要让j循环100次,而当中的x++和sum = sum + x;其实就是1+2+3+…+10000,也就是1002次,所以这个算法当中,循环部分的代码整体需要执行n2(忽略循环体头尾的开销)次。显然这个算法的执行次数对于同样的输入规模n = 100,要多于前面两种算法,这个算法的执行时间随着n的增加也将远远多于前面两个。

此时你会看到,测定运行时间最可靠的方法就是计算对运行时间有消耗的基本操作的执行次数。运行时间与这个计数成正比。

我们不关心编写程序所用的程序设计语言是什么,也不关心这些程序将跑在什么样的计算机中,我们只关心它所实现的算法。这样,不计那些循环索引的递增和循环终止条件、变量声明、打印结果等操作,最终,在分析程序的运行时间时,最重要的是把程序看成是独立于程序设计语言的算法或一系列步骤。

  • 同样问题的输入规模是n,求和算法的第一种,求 1+2+…+n需要一段代码运行n次。那么这个问题的输入规模使得操作数量是f(n)=n,显然运行100次的同一段代码规模是运算10次的10倍。
  • 而第二种,无论n为多少,运行次数都为1,即f(n) =1;第三种,运算100次是运算10次的100 倍。因为它是f(n) =n2

我们可以这样认为,随着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/2193,欢迎访问原出处。

不打个分吗?

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

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

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

大家都在看

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

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

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

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

《高性能网站建设指南》 桑德斯 (Steve Sounders) (作者), 刘彦博 (译者)

《高性能网站建设指南》结合Web2.0以来Web开发领域的最新形势和特点,介绍了网站性能问题的现状、产生的原因,以及改善或解决性能问题的原则、技术技巧和最佳实践。重点关注网页的行为特征,阐释优化Ajax、CSS、JavaScript、Flash和图片处理等要素的技术,全面涵盖浏览器端性能问题的方方面面。在《高性能网站建设指南》中,作者给出了14条具体的优化原则,每一条原则都配以范例佐证,并提供了在线支持。全书内容丰富,主要包括减少HTTP请求、ExpiresHeader技术、Gzip组件、CSS和JavaScript最佳实践、关闭ETags的技巧、Ajax缓存技术和最小化技术等。

更多计算机宝库...