第13话:算法的性能分析

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

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

  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本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

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

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

《高性能JavaScript》 Nicholas C. Zakas (作者), 赵泽欣 (合著者), 丁琛 (译者)

《高性能JavaScript》揭示的技术和策略能帮助你在开发过程中消除性能瓶颈。你将会了解如何提升各方面的性能,包括代码的加载、运行、DOM 交互、页面生存周期等。雅虎的前端工程师 Nicholas C. Zakas 和其他五位 JavaScript 专家介绍了页面代码加载的最佳方法和编程技巧,来帮助你编写更为高效和快速的代码。你还会了解到构建和部署文件到生产环境的最佳实践,以及有助于定位线上问题的工具。如果你使用 JavaScript 构建交互丰富的 Web 应用,那么 JavaScript 代码可能是造成你的Web应用速度变慢的主要原因。

更多计算机宝库...