算法效率分析基础讲义.ppt

文档介绍：正确性工作量空间用量简单性最优型12顺序查找:SequentialSearch(A[0..n-1],x)//输入:数组A[0..n-1],和查找关键字x//输出:返回第一个匹配x的元素下标//如果没有匹配的,返回-1i=0;whilei<nandA[i]≠xdoi=i+1;Ifi<nthenreturnielsereturn-1;?:问题规模越大,算法运行时间越长。将算法输入规模n为时间效率的参数。选择哪个(些)参数作为输入规模?7一个算法好不好体现在运行该算法所需要的计算机资源的多少上所需资源越少,该算法越好;计算机最重要的资源是时间和空间算法分析对算法利用这两种资源的效率做研究时间效率:指出正在讨论的算法运行得有多快;空间效率:关心算法需要的额外空间。研究实验告诉我们,对于大多数问题来说,我们在速度上能够取得的进展要远大于在空间上的进展,所以我们把主要精力集中在时间效率上。,分,小时吗?可以统计算法每一步的操作次数吗?一般的做法:把基本操作(最重要的操作)次数作为算法运行时间的度量单位。思考下面算法的重要操作:排序矩阵乘法9建立一个算法时间效率的分析框架对于输入规模为n的算法统计基本操作执行次数C(n),来对其效率进行度量。在某个特定计算机上的某个算法程序的运行时间T(n)≈copC(n)基本操作的执行时间基本操作次数10