[理学]计算理论与算法总复习12年6月.ppt

1.7 对偶与范式 计算理论与算法总复习 成绩计算方法 平时成绩 30% 上机题目 平时作业 平时考勤 期末成绩 70% 算法题中，严格按照题目要求给出算法代码、算法思想、测试用例的求解过程。 如果题目没有明确要求给出算法代码，那么不需要给出。 考题类型 判断题：10分. 5个 填空题：30分. 10个 大题：60分. 5道 CH1 算法概述 算法的五个特征 1）有穷性 2）确定性 3）输入 4）输出 5）可行性 算法的定义:Informally, an algorithm is any well-defined computational procedure that takes some value, or set of values, as input and produces some value, or set of values, as output. An algorithm is thus a sequence of computational steps that transform the input into the output. O、o、?、?、?第一种理解方法 设f和g是定义域为自然数N上的函数 f(n)=O(g(n)). 若存在正数c和n0使得对一切n?n0 有 0? f(n)?cg(n) f(n) =?(g(n)). 若存在正数c和n0使得对一切n?n0有 0? cg(n)? f(n) f(n) =o(g(n)). 若对任意正数c存在n0使得对一切n?n0有 0? f(n) cg(n) f(n) =?(g(n)). 若对任意正数c存在n0使得对一切n?n0有 0? cg(n) f(n) f(n) =?(g(n)) f(n) =O(g(n)) 且 f(n) =?(g(n)) O、o、?、?、?第二种理解方法 求复杂性函数阶的极限方法 标准复杂性函数的比较 O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn) 标准复杂性函数的比较 O(1)O(logn)O(n)O(nlogn)O(n2)O(n3)O(2n)O(n!)O(nn) 注意：1）不能划等号 2）以下若无特殊声明，log是以2为底的对数 3）上式只有在n较大的时候成立 O(1)的含义？ 计算时间由一个常数（零次多项式）来限界 例 例：算法A1,A2的时间复杂性分别是n,2n,设100μs是一个单位时间，求A1,A2在1s内能处理的问题规模。 已知lg2=0.301 例 假设某算法在输入规模为n的时间复杂性为T(n)=3*2n。在某台计算机上实现并完成该算法的时间为t秒。现在另一计算机，其运行速度为第一台的64倍，那么在这台新机器上用同一算法在t秒内能解输入规模为多大的问题？ 例 CH2 分治法 用分治法求n个元素集合S中的最大、最小元素。写出算法，并分析时间复杂性（比较次数）。 假设n=3m。要求每次平分成3个子集。 归并排序（Merge Sort) 主定理：其中n= ck, k为某个非负常数 归并排序 ?(nlogn) 快排序---划分过程 大整数乘法 求第k小的元素 线性时间选择问题: 线性时间选择: 中位数应用 中位数原理 X轴上有n个点，由左至右依次排列为 找一个点xp(不一定是n个点之一)，使xp到各 点距离和最小，解为： 【例】残缺棋盘 残缺棋盘是一个有2k×2k （k≥1）个方格的棋盘，其中恰有一个方格残缺。图中给出k=1时各种可能的残缺棋盘，其中残缺的方格用阴影表示。 ? 　 称作“三格板”，残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘。 问题分解过程： 以k=2时的问题为例，用二分法进行分解，得到如下图，用双线划分的四个k=1的棋盘。 循环赛日程表 循环赛日程表 循环赛日程表的推广 CH3 动归 方法概述: 基本思想 动态规划的思想实质是分治思想和解决冗余。 与分治法类似的是，将原问题分解成若干个子问题，先求解子问题，然后从这些子问题的解得到原问题的解。 与分治法不同的是，经分解的子问题往往不是互相独立的。若用分治法来解，有些共同部分（子问题或子子问题）被重复计算了很多次。 方法概述: 适用条件 动态规划法的有效性依赖于问题本身所具有的两个重要性质 最优子结构：当问题的最优解包含了其子问题的最优解时