什么叫算法分析?

发布网友发布时间：2024-01-19 07:05

共1个回答

热心网友时间：2024-01-23 23:08

回答如下：

目的是评价算法的效率，通过评价可以选用更加好更加适合的算法来完成。

算法分析

算法分析是对一个算法需要多少计算时间和存储空间作定量的分析。算法（Algorithm）是解题的步骤，可以把算法定义成解一确定类问题的任意一种特殊的方法。在计算机科学中，算法要用计算机算法语言描述，算法代表用计算机解一类问题的精确、有效的方法。

中文名

算法分析

外文名

Algorithm analysis

应用

算法优化

网络应用

引擎的算法应用

主要对象

时间复杂度、空间复杂度

作用

评价算法的好坏

简介

算法是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算，是对解题方案内的准确与完整地描述。制定一个算法，一般要经过设计、确认、分析、编码、测试、调试、计时等阶段。[1]

算法+数据结构=程序，求解一个给定的可计算或可解的问题，不同的人可以编写出不同的程序，来解决同一个问题，这里存在两个问题：一是与计算方法密切相关的算法问题；二是程序设计的技术问题。算法和程序之间存在密切的关系。分析算法可以预测这一算法适合在什么样的环境中有效地运行，对解决同一问题的不同算法的有效性作出比较。[1]

通常对于一个实际问题的解决，可以提出若干个算法，如何从这些可行的算法中找出最有效的算法呢？或者有了一个解决实际问题的算法后，如何来评价它的好坏呢？这些问题都需要通过算法分析来确定。评价算法分析性能的标准主要从算法执行时间和占用存储空间两个方面进行考虑，即通过分析算法执行所需要的时间和存储空间来判断一个算法的优劣。[2]

时间复杂度

一个程序的时间复杂度是指程序运行从开始到结束所需要的时间。

影响因素

一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固定数据类型的操作）构成的，其执行时间取决于两者的综合效果。为了便于比较同一问题的不同算法，通常的做法是：从算法中选取一种对于所研究的问题来说基本运算的原操作，以该原操作重复执行的次数作为算法的时间度量。一般情况下，算法中原操作重复执行次数是规模n的某个函数T(n)。许多时候要精确的计算T(n)是困难的，引入渐进时间复杂度在数量上估计一个算法的执行时间，也能够达到分析算法的目的。[3]

计算方法

计算时间复杂度的时候，主要考虑算法中最高阶项的开销，只要找出算法中最高阶的复杂度，就可以忽略低阶和常数的复杂度。[3]

引入数学符号“O”来估算算法时间复杂度，渐进时间复杂度的表示方法：F(n)=O(g(n))，其定义为，若F(n)和g(n)是定义在正整数集合上的两个函数，则F(n)=O(g(n))表示存在正的常数C和，使得当时，都满足。换句话说，就是这两个函数当整形自变量n趋于无穷大时，两者的比值是一个不等于0的常数。[3]

当要计算某个算法的时间复杂度F(n)时，可以找一个更简单的、阶数相同的简单算法g(n)等同计算，这里的g(n)是指替代函数，它具有和原算法一样更高阶复杂度。[3]

例如，一个程序的实际执行时间为：，则。使用O记号表示的算法的时间复杂度，称为算法的渐进时间复杂度。[3]

常见的渐进时间复杂度

通常用O(1)表示常数计算时间。常见的渐进时间复杂度有：

规则

为了便于估算一个算法的时间复杂度，我们约定一下几条可操作的规则：

（1）读写单个常量或单个变量、赋值、算术运算、关系运算、逻辑运算等，计为一个单位时间。

（2）条件语句if(C){s}，执行时间为（条件C的执行时间）+（语句块s的执行时间）。

（3）条件语句if(C)s1 else s2，执行时间为（条件C的执行时间）+（语句块s1和s2中执行时间最长的那个时间）。

（4）switch...case语句的执行时间是所有case子句中，执行时间最长的语句块。

（5）访问一个数据的单个元素或一个结构体变量的单个元素只需要一个单位时间。

（6）执行一个for循环语句需要的时间等于执行该循环体所需要时间乘上循环次数。

（7）执行一个while(C){s}循环语句或者执行一个do{s} while(C)语句，需要的时间等于计算条件表达式C的时间与执行循环s的时间之和再乘以循环的次数。

（8）对于嵌套结构，算法的时间复杂度由嵌套最深层语句的执行次数决定的。

（9）对于函数调用语句，它们需要的时间包括两部分，一部分用于实现控制转移，另一部分用于执行函数本身。[3]