知识点算法与算法的量度.pptVIP

1.3 算法和算法的量度 一个好的算法应该具有以下七个重要的特征： 　　算法可以使用自然语言、伪代码、流程图等多种不同的方法来描述。 1、有穷性（Finiteness） 　　算法的有穷性是指算法必须能在执行有限个步骤之后终止 2、确切性(Definiteness) 　　算法的每一步骤必须有确切的定义； 3、输入(Input) 　　一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件； 4、输出(Output) 　　一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的； 5、可行性(Effectiveness) 　　算法中执行的任何计算步都是可以被分解为基本的可执行的操作步，即每个计算步都可以在有限时间内完成；（也称之为有效性） 6、 高效性（High efficiency） 　　执行速度快，占用资源少； 7、 健壮性（Robustness） 　　对数据响应正确。 算法分析（时间复杂度、空间复杂度） 一般情况下重点考虑时间复杂度T(n) ： 因为时间复杂度代表了算法的数量级的思想,引入大O来表示。 如：前面介绍的T (n) = O(f(n))，利用大O可以表示为问题的规模，即 T (n) = O(f(n))=n;{ 说明问题的规模为n} 再比如： T (n) = O(f(n))=O（n2)= n2 { 说明问题的规模为n2 } 算法的时间复杂度定义—— 按照大Ο的定义，容易证明它有如下运算规则： （1） Ο(f)+O(g)=Ο(max(f,g))； （2） Ο(f)+ Ο(g)=Ο(f +g)； （3） Ο(f)-Ο(g)= Ο(f-g)； （4）如果g(N)= Ο(f(N))， 则Ο(f)+ Ο(g)= Ο(f)； （5）Ο(Cf(N))= Ο(f(N))，其中C是一个正的常数； 属于并行程序 （6） f =Ο(f)； 常见的时间复杂度，按数量级递增排序—— （1）常数阶 … … O(1)； （2）对数阶 … … ； （3）线性阶 … … ； O(n) (4) 线性对数阶 … … ； (5) 二次阶 … … ； (6) 立方阶 … … ； (7) K次方阶 … … ； (8) 2的指数阶 … … ； * * 1.3.1 算法 1.3.2 算法设计的原则 1.3.3 算法效率的衡量方法和准则 1.3.4 算法的存储空间需求 知识点三： 1.3.1 算法 1.3.2 算法设计的原则 设计算法时，通常应考虑达到以下的原则—— 1．正确性 2. 可读性 3．健壮性 4．高效率与低存储量需求 1.3.3 算法效率的衡量方法和准则 通常有两种衡量算法效率的方法: 事前分析估算法 事后统计法 上述都与算法执行时间相关的因素有关— 1）算法选用的策略 2）问题的规模 3）编写程序的语言 4）编译程序产生的机器代码的质量 5）计算机执行指令的速度 事前分析估算法 事后统计法 缺点之一：必须执行程序 缺点之二：其它因素掩盖算法本质 一个特定算法的“运行时间” 的大小，只依赖于问题的规模（通常用整数量n表示），或者说，它是问题规模的函数。 结论 假如，随着问题规模 n 的增长，算法执行时间的增长率和 f(n) （被认为是算法对应程序语句被执行的次数即语句频度）的增长率相同，则可记作——T (n) = O(f(n)) 称T (n) 为算法的(渐近)时间复杂度。。 算法的复杂性有时间复杂性和空间复杂性之分。 如何估算 算法的时间复杂度？ 算法的执行时间 = 原操作(i)的执行次数×原操作(i)的执行时间 （算法的执行时间）与（原操作执行次数之和） 成正比 定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)，它是n的某一函数 T(n)称为这一算法的“时间复杂性”。当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。我们常用大O表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大O表示只是说有上界，由定义如果f(n)=O(n)，那显然成立f(n)=O(n2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。 大Ο的性质 属于串行程序 例1时间复杂度: O(n3) 例 1