`
Tony_Lee-S
  • 浏览: 82280 次
  • 性别: Icon_minigender_1
  • 来自: 广州
社区版块
存档分类
最新评论

算法分析

阅读更多

资源的有效使用是评价一个软件质量的一个指标。完成某个任务的算法的有效性是确定程序执行速度的主要因素。虽然可以根据算法所用的内存量来分析算法的有效性,但是分析CPU时间往往更准确。然而通过测量两个算法的执行时间来比较算法是非常困难的。为了克服这些问题,计算机科学家开发了一个独立于计算机和指定输入的理论方法来分析算法。该方法大致估计了输入大小的改变而产生的影响。通过这个方法可以看到,随着输入大小的增长,算法执行时间增长得有多快,因此,可以通过检查两个算法的增长率来比较它们。

以线性查找为例。线性查找算法顺序比较数组中的元素与键值,直到找到键值或者数组已搜索完毕。如果该键值没有在数组中,那么对于一个大小为n的数组需要n次比较。如果该键值在数组中,那么平均需要n/2次比较。该算法的执行时间与数组的大小成正比。如果将数组大小加倍,那么,比较次数也会加倍。该算法是呈线性增长的,增长率是n的数量级。计算机科学家使用大O符号表示“数量级”。使用该符号,线性查找算法的复杂度就是O(n),读为“n阶”。

例如以下代码:

public static boolean search(double [] data, double target){
     int i;
     for (i = 0; i < data.length; i++){
          if (data[i] == target) return true;
     }
     return false;
}

 分析包含三个部分:

1、当for循环形开始时,完成了两个操作:第一个操作是将变量i初始化为0的赋值操作,另一个是执行测试,判断i是否小于data.length的操作。

2、当执行循环体时,由于要查找的数值在数组中不存在,因此循环体将执行n次。假设每执行一次循环体代需要k个操作,其中k是3或4左右的数值。所以循环体共执行了n次,第执行一次循环体需要k个操作,共执行了kn个操作。

3、循环结束后还有一个操作。

现在得到 的总操作娄是kn+3.但不管k有多大,可以看到,这个公式是线性的。所以算法的复杂度为O(n)。

对于相同的输入大小,算法的执行时间可能会随着输入的不同而不同。导致最短执行时间的输入称为最佳情况输入;而导致最长执行时间的输入称为最差情况输入。最佳和最差情况都不具有代表性,但是最差情况分析却是非常有用的。我们要确保自己的算法永远不会比最差情况还慢。平均情况分析试图在所有可能的相同大小输入中确定平均时间。平均情况分析是比较理想的,但是完成,这是因为对于许多问题而言,要确定各种输入实例的相对概率和分布是相当困难的。由于最差情况分析比较容易完成,所以,分析通常由最差情况主导。

如果要在线性表中查找一个已存在于线性表中的元素,那么线性查找在最差情况下需要n次比较,而在平均情况下需要n/2次比较。使用大O符号,这两种情况需要的时间都为O(n)。相乘常量(1/2)可以忽略。算法分析的重点在于增长率,而相乘常量对增长率没有影响。对于n/2或100n而言,增长率都和n一样。因此,O(n)=O(n/2)=O(100n)。

考虑在包含n个元素的数组中找出最大数据的算法。如果n为2,找到最大数需要一次比较;如果n为3,找到最大数需要再次比较。一般来况,在拥有n个无此的线性表中找到最大数需要n-1次比较。算法分析主要用于庞大的输入规模。如果输入规模较小,那么估计算法效率是意义的。随着n的增大,表达式n-1中的n就主导了复杂度。大O符号允许忽略非主导部分(例如,表达式n-1中的-1),并强调重要部分(例如,表达式n-1中的n)。因此,该算法的复杂度为O(n)。

我们用大O符号估计一个算法与输入规模相关的执行时间。如果执行时间与输入规模无关,该算法就称为耗费了常量时间,用符号O(1)表示。例如,在数组中从给定下标处获取元素的方法耗费的时间即称为常量时间,这是因为该时间不会随数组规模的增大而增长。

常用的增长函数的增长率的变化

函数 名称 n=25 n=50 f(50)/f(25)
O(1) 常量时间 1 1 1
O(log n) 对数时间 4.64 5.64 1.21
O(n) 线性时间 25 50 2
O(n*log n) 对数-线性时间 116 282 2.43
O(ne2) 二次时间 625 2500 4
O(ne3) 三次时间 15625 125000 8
O(2en) 指数时间 3.36*10e7 1.27*10e15 3.35*10e7

 

常见的递归函数

 

递归关系 结果 举例
T(n)=T(n/2)+O(1) T(n)=O(log n) 十分查找,欧几里得的GCD
T(n)=T(n-1)+O(1) T(n)=O(n) 线性查找
T(n)=2T(n/2)+O(1) T(n)=O(n)
T(n)=2T(n/2)+O(n) T(n)=O(nlog n)  归并排序
T(n)=2T(n/2)+O(nlog n) T(n)=O(nlog2 n)
T(n)=T(n-1)+O(n) T(n)=O(ne2) 选择排序、插入排序
T(n)=2T(n-1)+O(1) T(n)=O(2en) 汉诺塔
T(n)=T(n-1)+T(n-2)+O(1) T(n)=O(2en) 递归的斐波那契数
分享到:
评论

相关推荐

    吉林大学算法分析习题课答案.zip

    《吉林大学算法分析习题课答案》是一份与算法分析相关的学习资料,主要针对的是吉林大学算法分析课程的习题解答。这份压缩包文件包含了课件等教学资源,旨在帮助学生理解和掌握算法分析的核心概念、方法和技巧。下面...

    数据结构和算法分析 C++版 第三版

    "数据结构和算法分析 C++版 第三版" 本资源是《数据结构和算法分析 C++版 第三版》的摘要信息,作者是Clifford A. Shaffer,来自 Virginia Tech 的计算机科学系。该书将数据结构和算法分析的基本概念和技术进行了...

    数据结构与算法分析:Java语言描述 清晰中文+源代码

    《数据结构与算法分析:Java语言描述 第2版 》是国外数据结构与算法分析方面的经典教材 使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计) 随着计算机速度...

    中南大学算法分析与设计--课件

    《中南大学算法分析与设计》是一门深入探讨算法理论与实践的课程,其课件是学习者掌握算法精髓的重要参考资料。中南大学在该领域的教学有着较高的评价,虽然可能对于初学者而言稍显复杂,但对有志于深入算法研究的人...

    算法分析与设计陈慧南课后答案

    算法分析与设计陈慧南课后答案 本资源摘要信息总结了算法分析与设计的相关知识点,并对陈慧南课后答案的部分内容进行了详细的解释和分析。 一、最大公约数和循环次数 在算法分析中,最大公约数是非常重要的一个...

    算法分析与设计一书源程序(陈慧南)

    《算法分析与设计一书源程序》是由著名计算机科学家陈慧南编著的,这本书深入浅出地探讨了算法的设计技巧、分析方法以及其在实际问题中的应用。源程序是作者为了帮助读者更好地理解和实践书中理论而提供的实际代码...

    数据结构与算法分析_Java语言描述(第2版)

    数据结构与算法分析_Java语言描述(第2版).韦斯.pdf 个人收集电子书,仅用学习使用,不可用于商业用途,如有版权问题,请联系删除! 本书是国外数据结构与算法分析方面的经典教材,使用卓越的Java编程语言作为实现...

    算法分析与设计pdf

    《算法分析与设计》这本书是计算机科学领域的重要教材,它涵盖了算法设计的基本策略以及如何对这些算法进行效率分析。在编程世界中,算法是解决问题的关键,而理解和掌握算法分析与设计则是提升编程能力的重要步骤。...

    中北大学算法分析与设计实验报告

    **算法分析与设计** 在计算机科学领域,算法分析与设计是至关重要的组成部分,它涉及到如何高效地解决问题,并评估解决方案的性能。中北大学的这门课程旨在培养学生的算法思维、编程能力和问题解决能力。这份实验...

    数据结构与算法分析 C++语言描述 第4版

    本书是数据结构和算法分析的经典教材,书中使用主流的程序设计语言C++作为具体的实现语言。书中内容包括表、栈、队列、树、散列表、优先队列、排序、不相交集算法、图论算法、算法分析、算法设计、摊还分析、查找树...

    数据结构与算法分析(Java版)

    《数据结构与算法分析:Java语言描述 第2版 》是国外数据结构与算法分析方面的经典教材 使用卓越的Java编程语言作为实现工具讨论了数据结构(组织大量数据的方法)和算法分析(对算法运行时间的估计) 随着计算机速度...

    西南交通大学算法分析与设计(包含实验课程)作业全集附带答疑QQ

    《西南交通大学算法分析与设计课程解析及实验指南》 西南交通大学的人工智能专业在2022年的教学计划中,为学生们提供了一门至关重要的课程——“算法分析与设计”。这门课程旨在培养学生的逻辑思维能力和解决问题的...

    同济大学 《算法分析与设计》课件

    《算法分析与设计》是计算机科学中的核心课程,主要探讨如何设计有效的算法以及如何分析算法的性能。同济大学的这门课件涵盖了算法的多个关键方面,包括基础概念、设计策略、复杂度分析和应用实例。以下是根据提供的...

    北大屈婉玲算法分析课件和习题解答

    《北大屈婉玲算法分析课件与习题解答》是一份珍贵的学习资源,它涵盖了北京大学屈婉玲教授在算法分析课程中的教学内容和配套习题解答。这份资料旨在帮助学习者深入理解算法的本质,掌握算法设计与分析的核心技巧,...

    数据结构与算法分析习题答案

    数据结构与算法分析是计算机科学中的核心课程,它主要研究如何高效地组织和处理数据,以及设计和分析用于解决问题的算法。在这个主题中,我们涵盖了数组、链表、栈、队列、树、图、哈希表等基本数据结构,以及排序、...

    算法分析与设计教案算法分析与设计教案

    《算法分析与设计教案》是王晓东教授针对算法分析与设计这一重要计算机科学主题编写的教学资料,旨在帮助学生深入理解和掌握算法的核心概念、设计方法以及分析技巧。在这个压缩包中,包含的主要文件名为“计算机算法...

    算法分析与设计课下习题答案

    《算法分析与设计》是由屈婉玲等作者编写的教材,该书深入浅出地讲解了算法设计的基本原理和分析方法。课下习题是学习过程中不可或缺的一部分,它们旨在帮助学生巩固理论知识,提高实际问题解决能力。这些习题答案...

    数据结构和算法分析电子版

    标题“数据结构和算法分析电子版”所指向的知识点,首先是关于数据结构和算法分析这两个计算机科学的基础领域的探讨。数据结构主要涉及的是数据的组织、管理和存储方法,以便于更高效地访问和修改。它包括如数组、...

    数据结构与算法分析C++描述习题答案

    ### 数据结构与算法分析C++描述习题答案 #### 一、引言 《数据结构与算法分析C++描述习题答案》这本书是基于Mark Allen Weiss教授的经典教材《数据结构与算法分析》编写的答案手册。Weiss教授的原著被誉为20世纪最...

Global site tag (gtag.js) - Google Analytics