算法设计与分析

AlgorithmComplexity

1.渐进时间复杂性概念

算法复杂度是算法运行所需要的计算机资源的量,需要时间资源的量称为时间复杂性,需要的空间资源的量称为空间复杂性。在算法分析时,人们一般考虑时间复杂性。

直观的,人们容易用算法/程序执行某一个输入实例所需要的时间来衡量一个算法的时间复杂性。但是,算法执行时间是一个具体的量,容易受以下因素的影响:

1)计算机配置 计算机配置高,显然算法执行时间相对则短。
2)输入实例 输入实例不相同,算法执行时间一般也不同。
3)问题规模 输入实例的问题规模不相同,算法执行时间一般也不同。

时间复杂度不应该是在特定计算机上求解某一个输入实例所需要的执行时间;而应该是一个不依赖于计算机配置、输入实例和问题规模的抽象表示。因此,算法时间复杂性针对上述因素进行抽象:

1) 元操作计数 考虑算法中元操作的执行总数。
2) 输入特化 对于相同问题规模的输入实例,只考虑最差情况下的输入实例。
3) 函数简化 略去复杂度函数的低阶项,仅保留高阶项。

定义1:渐进复杂性

对于算法A的复杂性函数,如果存在,使得当时有,那么就称为算法A当的渐近复杂性。

定义2. 大O记号

设f(N)和g(N)是定义在正数集上的正函数,如果存在正的常数C和自然数N0,使得当N≥N0时有f(N) ≤Cg(N),则称函数f(N)当N充分大时上有界,g(N)是f(N)的一个上界,记为f(N) = O(g(N)),即f(N)的阶不高于g(N)的阶。

2.算法时间复杂度分析

1)非递归算法的复杂性分析

非递归算法一般由串行语句段和循环语句构成,其中循环语句是时间复杂性分析的关键。非递归算法的复杂性分析包括以下三个步骤:

确定关键操作 关键操作可以是高级程序设计语言中的赋值、比较、算术运算、逻辑运算、读写单个常量或单个变量等操作(一般被看作是基本操作,并约定所用的时间都是一个单位);也可以是由常数个基本操作构成的程序块。
计算关键操作总的执行步数 ,一般是数列和的形式。
求解渐进阶,并用O(.)表示

2)递归算法的复杂性分析

假定递归过程(或函数)所需要的时间为一个待定函数(函数的自变量为递归程序的输入规模);然后根据递归调用建立时间复杂性函数的递推方程;最后求解递推方程得到时间复杂性。其复杂性分析过程包括以下三个步骤:

分析递归程序的结构,确定每一逻辑块的时间复杂性 非递归的程序块(或者子函数)用非递归方法分析其复杂性;递归函数的复杂性则跟据其输入规模递归地表示。
构造复杂性函数的递推方程。
求解递归方程和渐进阶,并用O(.)表示。


3.课件下载

Algorithm-2-Asymptotic Analysis

4.扩展阅读

随着硬件技术的发展,计算机体系结构已经普遍采用多核架构;面向大数据挑战,应用系统则应用分布式算法和系统。面对这些情景,算法复杂度分析也需要进行相应的改进,除了计算指令的开销,我们还需要考虑通信开销和数据 I/O的开销等因素。建议大家阅读以下文献:

Ref-1-1: 施特拉森矩阵乘法的通信成本