您现在的位置:首页 > >

计算机算法设计与分析第4版第1章ppt课件

发布时间:

计算机算法设计与分析(第4版) 第1章 算法概述 学习要点: ? 理解算法的概念。 ? 理解什么是程序,程序与算法的区别和内在联系。 ? 掌握算法的计算复杂性概念。 ? 掌握算法渐近复杂性的数学表述。 ? 掌握用C++语言描述算法的方法。 算法(Algorithm) ? 算法是指解决问题的一种方法或一个过程。 ? 算法是若干指令的有穷序列,满足性质: ? (1)输入:有外部提供的量作为算法的输入。 ? (2)输出:算法产生至少一个量作为输出。 ? (3)确定性:组成算法的每条指令是清晰,无歧义的。 ? (4)有限性:算法中每条指令的执行次数是有限的,执 行每条指令的时间也是有限的。 程序(Program) ? 程序是算法用某种程序设计语言的具体实现。 ? 程序可以不满足算法的性质(4)。 ? 例如操作系统,是一个在无限循环中执行的程序,因 而不是一个算法。 ? 操作系统的各种任务可看成是单独的问题,每一个问 题由操作系统中的一个子程序通过特定的算法来实现。 该子程序得到输出结果后便终止。 问题求解(Problem Solving) 理解问题 精确解或近似解 选择数据结构 算法设计策略 设计算法 证明正确性 分析算法 设计程序 算法复杂性分析 ? 算法复杂性 = 算法所需要的计算机资源 ? 算法的时间复杂性T(n); ? 算法的空间复杂性S(n)。 ? 其中n是问题的规模(输入大小)。 算法的时间复杂性 ? (1)最坏情况下的时间复杂性 ? Tmax(n) = max{ T(I) | size(I)=n } ? (2)最好情况下的时间复杂性 ? Tmin(n) = min{ T(I) | size(I)=n } ? (3)平均情况下的时间复杂性 ? ? Tavg(n) = p(I)T(I) siz(eI)?n ? 其中I是问题的规模为n的实例,p(I)是实 例I出现的概率。 算法渐近复杂性 ? T(n) ?? , as n?? ; ? (T(n) - t(n) )/ T(n) ?0 ,as n??; ? t(n)是T(n)的渐近性态,为算法的渐近复杂性。 ? 在数学上, t(n)是T(n)的渐近表达式,是T(n)略去低阶 项留下的主项。它比T(n) 简单。 渐近分析的记号 ? 在下面的讨论中,对所有n,f(n) ? 0,g(n) ? 0。 ? (1)渐近上界记号O ? O(g(n)) = { f(n) | 存在正常数c和n0使得对所有n? n0有: 0 ? f(n) ? cg(n) } ? (2)渐近下界记号? ? ? (g(n)) = { f(n) | 存在正常数c和n0使得对所有n? n0有: 0? cg(n) ? f(n) } ? (3)非紧上界记号o ? o(g(n)) = { f(n) | 对于任何正常数c>0,存在正数和n0 >0使得对所有n? n0有:0 ? f(n)<cg(n) } ? 等价于 f(n) / g(n) ?0 ,as n??。 ? (4)非紧下界记号? ? ? (g(n)) = { f(n) | 对于任何正常数c>0,存在正数和n0 >0使得对所有n? n0有:0 ? cg(n) < f(n) } ? 等价于 f(n) / g(n) ?? ,as n??。 ? f(n) ? ? (g(n)) ? g(n) ? o (f(n)) ? (5)紧渐近界记号? ? ? (g(n)) = { f(n) | 存在正常数c1,c2和n0使得对所有n? n0 有:c1g(n) ? f(n) ? c2g(n) } ? 定理1: ? (g(n)) = O (g(n)) ? ? (g(n)) 渐近分析记号在等式和不等式中的意义 ? f(n)= ?(g(n))的确切意义是:f(n) ? ?(g(n))。 ? 一般情况下,等式和不等式中的渐近记号?(g(n))表示 ?(g(n))中的某个函数。 ? 例如:2n2 + 3n + 1 = 2n2 + ?(n) 表示 ? 2n2 +3n +1=2n2 + f(n),其中f(n) 是?(n)中某个函数。 ? 等式和不等式中渐近记号O,o, ?和?的意义是类似的。 渐近分析中函数比较 ? f(n)= O(g(n)) ? a ? b; ? f(n)= ?(g(n)) ? a ? b; ? f(n)= ?(g(n)) ? a = b; ? f(n)= o(g(n)) ? a < b; ? f(n)= ?(g(n)) ? a > b. 渐近分析记号的若干性质 ? (1)传递性: ? f(n)= ?(g(n)), g(n)= ?(h(n)) ? f(n)= ?(h(n)); ? f(n)= O(g(n)), g(n)= O (h(n)) ? f(n)= O (h(n)); ? f(n)= ?(g(n)), g(n)= ? (h(n)) ? f(n)= ?(h(n)); ? f(n)= o(g(n)), g(n)= o(h(n)) ? f(n)= o(h(n)); ? f(n)= ?(g(n)), g(n)= ? (h(n)) ? f(n)= ? (h(n)); ? (2)反身性: ? f(n)= ?(f(n)); ? f(n)= O(f(n)); ? f(n)= ?(f(n)). ? (3)对称性: ? f(n)= ?(g(n)) ? g(n)= ? (f(n)) . ? (4)互对称性: ? f(n)= O(g(n)) ? g(n)= ? (f(n)) ; ? f(n)= o(g(n)) ? g(n)= ? (f(n)) ; ? (5)算术运算: ? O(f(n))+O(g(n)) = O(max{f(n),g(n)}) ; ? O(f(n))+O(g(n)) = O(f(n)+g(n)) ; ? O(f(n))*O(g(n)) = O(f(n)*g(n)) ; ? O(cf(n)) = O(f(n)) ; ?


热文推荐
猜你喜欢
友情链接: 简历 面试求职范文 职业规划 自我管理 社交礼仪 76242百科