JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 《疯狂的石头》剪辑:道哥的计划 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 道哥缺乏概括能力,无法清晰表达自己的方法(算法) JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 《三国演义》剪辑:隆重对策 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 隆重对策,鞭辟入里。 三分天下,人神共奋。 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 问题:伸大义于天下 环境:曹操,…… 孙权,…… 荆州,…… 益州,…… JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 方案:跨荆州、益州…… 向西,……;向南,…… 对外,……;对内,…… 荆州之兵 + 益州,…… JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 设计算法,首先要有总括能力:分析问题准确、细致;解决问题条分缕析、主次得当。 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 第 5 章 归纳法 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 几个最基础的排序算法 选择排序 插入排序 冒泡排序 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 基数排序 整数列 L= 7467、1247、3275、6792、9187、9134、4675、1239 基数:10 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin L0= L1= L2= L3= L4= L5= L6= L7= L8= L9= 生成10个空表 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin L0= L1= 6792 L2= L3= 9134 L4= 3275、4675 L5= L6= 7467、1247、9187 L7= L8= 1239 L9= 按个位进表 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 归拢这十个表表 6792、9134、3275、4675、7467、1247、9187、1239 L= JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin L0= L1= L2= 9134、1239 L3= 1247 L4= L5= 7467 L6= 3275、4675 L7= 9187 L8= 6792 L9= 按十位进表 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 二次归拢这十个表表 9134、1239、1247、7467、3275、4675、9187、6792 L= JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin L0= 9134、9187 L1= 1239、1247、3275 L2= L3= 7467 L4= L5= 4675 L6= 6792 L7= L8= L9= 按百位进表 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 三次归拢这十个表表 9134、9187、1239、1247、3275、7467、6475、6792 L= JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin L0= 1239、1247 L1= L2= 3275 L3= 4675 L4= L5= 6792 L6= 7467 L7= L8= 9134、9187 L9= 按千位进表 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 四次归拢这十个表表 1239、1247、3275、6475、6792、7467、9134、9187 L= JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 数位不同,可以分别处理。 基数可变:2、4、8、10、16… 算法重点:生成空白表、进表 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 算法RadixSort: 输入:一张有n个非负整数的表L={a1, …, an},每个数 k位 输出:按照非降序排列的L JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin for j =1 to k 生成 10 个空表 L0, L1, …, L9 while L 非空 a = L 中的下一个元素 L(next);删除 L(next) i = a 中的第 j 位数字; 数 a 进表 Li end while for i = 0 to 9 L = L, Li , 将 Li 加入 L 中 end for return L JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 开始 流程图 j=1 jk? Y 生成10个表,L0,…,L9 结束 j++ i=0 N Y L 非空? N N i 9? a = L(next); Delete(L(next)) i = a 的第 j 位数; a 进表 Li L = L Li JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 算法RadixSort的复杂度:θ(kn) 思考:对于位数不相等的整数序列,如何用该算法排序? JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 一个看似简单、直接的问题,竟然有意想不到的巧妙解法,从这可见算法设计的 魅力所在。 算法不是从地里长出来的,是人们经过艰辛的努力发现的!它们象下面的原子模型的建立过程 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 原子模型建立过程 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 启发: 大胆设计算法,不断改进之。 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 这个问题是如何计算一个实数的整数幂, xn ? 直接求解 :连续累乘 算法简单,效率较高! JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 竟然有个更为高效、颇为简单的算法!!! 如果 n 是偶数, xn = (xm)2 如果 n 是奇数,xn = x(xm)2 聪明吧! JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 算法 EXPREC 描述 输入:实数 x 和非负整数 n 输出: xn JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin power( x, n ) 过程 power( x, m ) { 计算 xm } if m = 0 then y = 1 else y = y = y2 if m 为奇数 then y =xy end if return y JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin power( x, m )流程图 开始 y = y = y2 Y N m = 0? y = 1 N m 是奇数? Y y = xy 返回 y 结束 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 练习: 实现这两个算法 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 寻找多数元素——强针对性算法 多数元素——对序列A[1…n],如果有出现次数超过 的元素,这个元素就叫该序列的多数元素。 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 办法很多 现成的办法有两个 1、一一比较,时间复杂度 O(n2) 2、排序,时间复杂度 O(nlogn) 还有,更简单的算法!! JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 算法基础 在原序列中,消除两个不同的元素后,原序列中的多数元素仍然是新系列中的多数元素。 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 算法关隘: 如何在原序列中,不断地、高效地去除两个不同的元素,直至最后? 显然是顺次嘛! JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 算法步骤: 输入:n个元素的数组 A[1…n] 输出:如果存在多数元素,则输出之;否则输出 none JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin c = candidate(1) count = 0 for j = 1 to n if A[j] = c then count = count + 1 end for if count > then return c else return none JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 开始 算法流程图 c = candidate(1) count = 0 j = 1 to n N A[j]=c? Y count ++ N Y 返回 none 返回 c 结束 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 过程:candidate( m ) j = m; c = A[m]; count = 1 while j<n && count > 0 j = j + 1 if A[j] = c then count ++ else count -- end while if j = n then return c else return candidate (j + 1) JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin m candidate( m ) 流程图 j = m; c = A[m]; count = 1 j <n && count > 0 N A[j]=c? Y count -- count ++ N j = n ? Y 返回 candidate(j+1) 返回 c JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 如果数组中有多数元素,即使全部“非多数元素”都被用来去除“这个多数元素”,最终留下的必是这个多数元素。 思考: 如果原序列中没有多数元素,由 candidate(m) 带回来的元素 c 有什么特征? 比如是最后一个元素?至少重复一次?…… JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 简单的证明思路: 每当消除数组中的一个多数元素,必定至少有一个 “非多数元素” 同时被消除,根据 “多数元素”的定义,最终留下的必是这个多数元素。 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 堆排序 利用二叉树构成的堆——二叉堆,对数列排序。 由于二项式堆、斐波纳契堆等使用较少,一般将二叉堆就简称为堆。 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 堆的特性: 1.父节点的键值大于或等于(小于或等于)每个子节点的键值。 2.每个节点的左子树和右子树都是一个堆。 注: 特性 1 中,前者为 “最大堆” 或者 “大顶堆”,后者为 “最小堆” 或者 “小顶堆”。 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 堆的存储:(1)二叉树 12 35 22 7 8 32 10 1 15 5 23 27 9 4 A[14] = 用数组来表示二叉树,节点 i (= 0, 1, 2, …)的父结点下标就为 (i – 1) / 2。它的左右子节点下标分别为 2 * i + 1 和 2 * i + 2。例如,第 4个节点左右子节点下标分别为 9 和 10 。见下图。 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 堆的存储:(1)二叉树例图 12 35 22 7 8 32 10 1 15 5 23 27 9 4 A[14] = 12 35 22 7 8 32 10 4 1 9 27 23 5 15 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 堆的存储:(2) 堆(最大堆) 35 23 32 15 12 27 10 1 7 5 8 22 9 4 A[14] = 35 23 32 15 12 27 10 4 1 9 22 8 5 7 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 建堆: 从最后一个中间节点开始。n = 14,不大于 n/2 的最大整数是 7 ,节点 7 的键值 = 10。按照定义,该子树是最大堆,不需要调整这两个节点的键值。 之后考察 i = 5 的节点,其键值 32,该子树也是最大堆, 但是, i = 4 的节点所在子树不是最大堆,所以要调整, …… JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 起始图: 12 35 22 7 8 32 10 4 1 9 27 23 5 15 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 注意 i = 4 、 i = 10 和 i = 3 、 i = 8 的节点键值的变化 12 35 22 15 23 32 10 4 1 9 27 8 5 7 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 继续查看 i = 2 和 i = 1 的节点,于是有下图 注意 i = 5 和 i = 11 的节点键值的变化 12 35 32 15 23 27 10 4 1 9 22 8 5 7 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 注意 i = 5 和 i = 11 的节点键值的变化 35 23 32 15 12 27 10 4 1 9 22 8 5 7 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 完成最大堆的构建 注意:每一步都要到数组中修改相应位置的元素值 35 23 32 15 12 27 10 4 1 9 22 8 5 7 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 建堆结果: 1、序列成为一个“最大堆”; 2、根节点键值是序列的最大数。 JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 堆排序: 建堆 j = , …, 1 while i = 1, …, n-1 对换节点 k = n+1-i 与节点 k = 1 Sift-down(H-i, 1) // 序列最后的 i 个元素已经排好序 end while return JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 堆的运算——上筛 Sift-up(H, i) 目标:上移 H[i] 使得他的键值不大于其父节点的 flag = 0; if(i = 1) then exit; //节点 i 为根节点 while i = 1 or flag = 1 if( H(i) > H( ) ) then 对换这两个节点 else flag = 1 i = end while return JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 堆的运算——下筛 Sift-down(H, i) 目标:下移 H[i] 使得他的键值不大于其父节点的 flag = 0; if( 2i > n ) then exit; //节点 i 为叶子节点 while 2i > n or flag = 1 i = 2i if (i+1n && H(i+1) > H( i ) ) then i = i+1 if( H(i) > H( ) ) then 对换这两个节点 else flag = 1 end while return JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 堆的运算——插入 Insert(H, x) 目标:向堆 H 中插入一个元素 x n = n+1; //增加 H 的大小 H[n] = x Sift-up(H, n) JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 堆的运算——删除 Delete(H, i) 目标:删除堆中元素 H[i] x = H[i]; y = H[n]; n = n-1 //减少 H 的大小 if( i=n+1) then exit; H[i] = y if( yx ) then Sift-up( H, i ) else Sift-down( H, i ) end if JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 堆的运算——删除最大值 DeleteMax( ) 目标:删除堆中最大元素 x x = H[1]; n = n-1 //减少 H 的大小 delete( H, 1) H[i] = y return x JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 堆的运算——建堆 MakeHeap(A) 目标:将一个 n 元数组 A,转化为一个堆 for i = down to 1 Sift-down( A, i ) end for JUFE • SCES__Dr. Aihua Yin 2019/5/10
JUFE • SCES__Dr. Aihua Yin 练习 实现这两个算法 本章结束! JUFE • SCES__Dr. Aihua Yin 2019/5/10