第4讲算法效率ppt课件

1、第4讲 算法效率1内容提要什么是算法算法的设计目的算法分析时间复杂度算法的空间复杂度2 1. 算法 算法的定义和算法的表示方法算法是描画求解问题方法的操作步骤集合。算法要用某种言语来描画。常用的算法描画方法：自然言语程序设计言语类程序设计言语流程图算法的性质输入性：具有零个或假设干个输入量；输出性：至少产生一个输出或执行一个有意义操作；有限性：执行语句的序列是有限的；确定性：每一条语句的含义明确，无二义性；可执行性：每一条语句都应在有限的时间内完成。 2. 算法设计目的 算法设计应满足以下五条目的：正确性 可读性 强壮性 高时间效率 高空间效率3. 算法分析对于一个问题，一旦某种算法给定并且是

2、正确的，那么最重要的就是确定该算法将需求多少诸如时间或空间等资源的问题。估计算法资源耗费所需的分析是一个实际问题，需求一套系统架构。数学根底定义1 假设存在正常数c和n0使得当Nn0时T(N) cf(N)，那么记为T(N)=O(f(N)定义2 假设存在正常数c和n0使得当Nn0时T(N) cg(N)，那么记为T(N)= (g(N)定义3 T(N)=(h(N)当且仅当T(N)=O(h(N)和T(N)= (h(N)定义4 假设对每一正常数c都存在常数n0使得当Nn0时T(N)cp(N)，那么T(N)=o(p(N)数学根底这些定义的目的是要在函数间建立一种相对的根本，比较的是它们的相对增长率例如：1

3、000N=O(N2)大O标志法当T(N)=O(f(N)时，函数T(N)是在以不快于f(N)的速度增长，因此f(N)是T(N)的一个上界f(N)=(T(N)，T(N)是f(N)的一个下界数学根底法那么1：假设T1(N)=O(f(N)且T2(N)=O(g(N)，那么T1(N)+T2(N)=O(f(N)+g(N)可写成max(O(f(N),O(g(N)T1(N)*T2(N)=O(f(N)*g(N)法那么2：假设T(N)是一个k次多项式，那么T(N)=(Nk)法那么3：对恣意常数k，logkN=O(N)函数名称c常数logN对数log2N对数平方的N线性的NlogNN2二次的N3三次的2N指数的数学根

4、底将常数或低阶项放进大O是坏习惯经过极限 来确定两个函数f(N)和g(N)的增长率，必要的时候可以运用洛比达法那么。该极限可以有四种能够的值：极限是0：f(N)=o(g(N)极限是c0：f(N)=(g(N)极限是：g(N)=o(f(N)极限摆动：二者无关要分析的问题要分析的最重要的资源就是运转时间和算法执行时间相关的要素：1算法选用的战略2问题的规模3编写程序的言语4编译程序产生的机器代码的质量5计算机执行指令的速度一个特定算法的“运转任务量的大小，只依赖于问题的规模通常用整数量n表示，或者说，它是问题规模的函数。 定义两个函数Tavg(N)和Tworst(N)，分别为算法对于输入量N所破费的

5、平均运转时间和最坏情况的运转时间普通情况下，计算的是最坏情况的运转时间T (n) 为算法的(渐近)时间复杂度如何估算算法的时间复杂度？ 从算法中选取一种对于所研讨的问题来说是 根本操作 的原操作，以该根本操作 在算法中反复执行的次数频度作为算法运转时间的衡量准那么.由于: 算法 = 控制构造 + 原操作固有数据类型的操作 算法的执行时间=原操作(i)的执行次数原操作(i)的执行时间 算法的执行时间 与 原操作执行次数之和 成正比一个简单的例子public static int sum(int n) int partialSum; partialSum=0; for(int i=1;i=n;i+

6、) partialSum+=i*i*i; return partialSum;不计时间114N1、N+1、N估算算法的时间复杂度的方法:1.多数情况下,求最深层循环内的简单语句(原操作)的反复执行的次数.2.当难以准确计算原操作的执行次数时,只需求出它关于n的增长率或阶即可.3.当循环次数未知(与输入数据有关),求最坏情况下的简单语句(原操作)的反复执行的次数. 例1: for (i=1; i=n; +i) for (j=1; j=n; +j) cij = 0; for (k=1; k=n; +k) cij += aik*bkj; 根本操作: 乘法操作时间复杂度: O(n3) 计算算法的时间复

7、杂度的例题:例2:void select_sort(int a) int n=a.length,temp; for ( i = 0; i n-1; +i ) j = i; for ( k = i+1; k n; +k ) if (ak 1 & change; -i) change = false; for (j=0; j aj+1) temp=aj;aj=aj+1;aj+1=temp; change = TRUE ； / bubble_sort根本操作: 赋值操作 时间复杂度: O(n2) 计算算法的时间复杂度的例题:例4： +x;s=0;根本操作： 时间复杂度为：+x或s=0(1) 即常量阶

8、计算算法的时间复杂度的例题:计算算法的时间复杂度的例题:if (list.contains(e) System.out.println(e);else for (Object t: list) System.out.println(t); 22T(n) = test time + worst-case (if, else) = O(n) + O(n) = O(n)Time ComplexityLet n be list.size().Executedn times.O(n)例5：其关系为：O(1)O(logn)O(n)O(nlogn)O(n2)O(n3) 指数时间的关系为：O(2n)O(n!)

9、=2递归的斐波那契数的时间复杂度Since27and 实例: 非递归斐波那契数列 public static long fib(long n) long f0 = 0; / For fib(0) long f1 = 1; / For fib(1) long f2 = 1; / For fib(2) if (n = 0) return f0; else if (n = 1) return f1; else if (n = 2) return f2; for (int i = 3; i = n; i+) f0 = f1; f1 = f2; f2 = f0 + f1; return f2; 28这个

10、算法的时间复杂度为29 f0 f1 f2Fibonacci series: 0 1 1 2 3 5 8 13 21 34 55 89 indices: 0 1 2 3 4 5 6 7 8 9 10 11 f0 f1 f2Fibonacci series: 0 1 1 2 3 5 8 13 21 34 55 89 indices: 0 1 2 3 4 5 6 7 8 9 10 11 f0 f1 f2Fibonacci series: 0 1 1 2 3 5 8 13 21 34 55 89 indices: 0 1 2 3 4 5 6 7 8 9 10 11 f0 f1 f2Fibonacci series: 0 1 1 2 3 5 8 13 21 34 55 89 indices: 0 1 2 3 4 5 6 7 8 9 10 11 实例：找素数比较以下四种算法:30穷举法检测到 Math.sqrt(n)检测到 Math.sqrt(n)的素数挑选法PrimeNumberEfficientPrimeNumbersSieveOfEratosthemesPrimeNumb