《{企业效率管理}第4讲算法效率》由会员分享，可在线阅读，更多相关《{企业效率管理}第4讲算法效率（33页珍藏版）》请在金锄头文库上搜索。
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),数学基础,这些定义的目的是要在函数间
3、建立一种相对的基本，比较的是它们的相对增长率 例如：1000N=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),数学基础,将常数或低阶项放进大O
4、是坏习惯 通过极限 来确定两个函数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(in
6、t i=1;i=n;i+) partialSum+=i*i*i; return partialSum; ,不计时间,1,1,4N,1、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; 基本操作: 乘法操
7、作 时间复杂度: O(n3),计算算法的时间复杂度的例题:,例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 aj ) j = k; if ( j != i ) temp=ai;ai=aj;aj=temp; / select_sort 基本操作: 比较(数据元素)操作 时间复杂度: O(n2),计算算法的时间复杂度的例题:,例3: void bubble_sort(int a) int n=a.length,temp;
8、boolean change; for (i=n-1, change=true; i1 change = TRUE ； / bubble_sort 基本操作: 赋值操作 时间复杂度: O(n2),计算算法的时间复杂度的例题:,例4： +x;s=0; 基本操作： 时间复杂度为：,+x或s=0,(1) 即常量阶,计算算法的时间复杂度的例题:,计算算法的时间复杂度的例题:,if (list.contains(e) System.out.println(e); else for (Object t: list) System.out.println(t); ,22,T(n) = test time +
9、 worst-case (if, else) = O(n) + O(n) = O(n),Time Complexity,O(n),例5：,其关系为： O(1)O(logn)O(n)O(nlogn)O(n2)O(n3) 指数时间的关系为： O(2n)O(n!)O(nn),常用计算算法时间的多项式,分析二分查找算法,算法中的每次迭代都包含一个常数操作，记做 c . 假设n 是2的幂， k=logn. 经过一次比较，二分查找排除了一半的输入,24,分析汉诺塔问题,c 表示移动一个盘子的常量时间，也就是说 T(1)=c. 则,25,实例分析: Fibonacci 数,/* The method for
10、 finding the Fibonacci number */ public static long fib(long index) if (index = 0) / Base case return 0; else if (index = 1) / Base case return 1; else / Reduction and recursive calls return fib(index - 1) + fib(index - 2); ,26,Finonacci series: 0 1 1 2 3 5 8 13 21 34 55 89 indices: 0 1 2 3 4 5 6 7
11、8 9 10 11 fib(0) = 0; fib(1) = 1; fib(index) = fib(index -1) + fib(index -2); index =2,递归的斐波那契数的时间复杂度,Since,27,and,实例: 非递归斐波那契数列,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 =
12、2) return f2; for (int i = 3; i = n; i+) f0 = f1; f1 = f2; f2 = f0 + f1; return f2; ,28,这个算法的时间复杂度为,29,f0 f1 f2 Fibonacci 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 f2 Fibonacci 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 f2 Fibona
13、cci 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 f2 Fibonacci 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)的素数 筛选法,PrimeNumber,EfficientPrimeNumbers,SieveOfEratosthemes,PrimeNumbers,实例: 最近的点对,31,实际考虑,虽然时间复杂度的分析是一种很好的理论估计算法效率的方式，但是两个算法具有意义的时间复杂度不代表效率相同。,32,4 .算法的空间复杂度分析 算法的空间复杂度分析主要是分析算法在运行时所需要的内存空间的数量级。算法的空间复杂度通常也采用O()函数。 算法的空间复杂度分析方法和算法的时间复杂度分析方法类同。,
