算法效率的度量和存储空间需求.pdf

算法效率的度量和存储空间需求CompanyDocumentnumber:WUUT-WUUY-WBBGB-BWYTT-1982GT本课主题:算法效率的度量和存储空间需求教学目的:掌握算法的渐近时间复杂度和空间复杂度的意义与作用教学重点:渐近时间复杂度的意义与作用及计算方法教学难点:渐近时间复杂度的意义授课内容:一、算法效率的度量算法执行的时间是算法优劣和问题规模的函数。评价一个算法的优劣可以在相同的规模下考察算法执行时间的长短来进行判断。而一个程序的执行时间通常有两种方法：1、事后统计的方法。缺点：不利于较大范围内的算法比较。（异地异时异境）2、事前分析估算的方法。程序在计算机上运行所需时间的影响因素算法木身选用的策略问题的规模规模越大消耗时间越多书写程序的语言语言越高级消耗时间越多编译产生的机器代码质量机器执行指令的速度综上所述为便于比较算法本身的优劣应排除其它影响算法效率的因素。从算法中选取一种对于所研究的问题来说是基本操作的原操作以该基木操作重复执行的次数作为算法的时间量度。(原操作在所有该问题的算法中都相同)7'(n)=6?(f(n))上示表示率和f(n)的增长率相同称作算法的渐近时间复杂度简称时间复杂度。sum(intnum[4][4]){intijr=0;求4*4矩阵元素和for(i=0;i<4;i++)T(4)=0(f(4))for(j=0;j<4;j++)f二n*n;r+=num[i][j];/*原操作*/returnr;}ispass(intnum[4][4]){intij；最好情况：T(4)二0for(i=0;i<4;i++)(0)for(j=0;j〈4;j++)最坏情况：if(num[i][j]!=i*4+j+l)T(4)=0return0;(n*n)return1;}原操作执行次数和包含它的语句的频度相同。语句的频度指的是该语句重复执行的次数。语句频度时间复杂度{++x;s=0;}10(1)for(i=l;i<=n;++i)n0(n){++x;s+=x;}for(j=l;j<=n;++j)for(k=l;k<=n;++k)n*n0(n*n){++x;s+=x；}O(logn)基木操作的执行次数不确定时的时间复杂度依基本操作执行次数概率计平均时间复杂度算平均在最坏情况下基本操作执行最坏情况下时间复杂度次数二、算法的存储空间需求类似于算法的时间复杂度空间复杂度可以作为算法所需存储空间的量度。记作: