中国高校课件下载中心 》 教学资源 》 大学文库

北京大学:《数据结构与算法》课程教学资源(实习讲义)算法优化

文档信息
资源类别:文库
文档格式:PPT
文档页数:25
文件大小:652KB
团购合买:点击进入团购
内容简介
北京大学:《数据结构与算法》课程教学资源(实习讲义)算法优化
刷新页面文档预览

算优化

算法优化 贾由

为什么先讲算法优化? 算法优化不是高级算法 算法优化是关于算法的思维方式 化孤立为体系

为什么先讲算法优化? ▪ 算法优化不是高级算法 ▪ 算法优化是关于算法的思维方式 ▪ 化孤立为体系

主要意图 ■提供一些有普遍性、有启发性的优化模式 从一个已有算法,大概知道可以从哪些方 面着手提高它的性能

主要意图 ▪ 提供一些有普遍性、有启发性的优化模式 ▪ 从一个已有算法,大概知道可以从哪些方 面着手提高它的性能

内容框架 数据结构与优化 动态规划的优化 搜索的优化 贪心与优化

内容框架 ▪ 数据结构与优化 ▪ 动态规划的优化 ▪ 搜索的优化 ▪ 贪心与优化

数推施判 两个启发小夹倒

数据结构 两个启发性实例

块状链表(1) ■向量 定位0(1),增奶0(m) 链表 定位0(m),增奶0(1) 块状链表 定位0(m12),增奶0(m12)

块状链表(1) ▪ 向量 • 定位O(1),增删O(n) ▪ 链表 • 定位O(n),增删O(1) ▪ 块状链表 • 定位O(n1/2),增删O(n1/2)

块状链表(2) 8 006-[4_□→[0 Ato Inserto Erase( Update Maxo Min(- RMQ 常被用在别的复杂算法中来降低复杂度 如CA的0(m)-0(1)算法

块状链表(2) ▪ 常被用在别的复杂算法中来降低复杂度 • 如LCA的O(n) – O(1)算法 0 0 60 4 0 61 3 1 2 At() Insert() Erase() Update() Max() Min() - RMQ

后继数组(1) ■问题:给一个纸条涂色,每次用某种颜色 涂某个连续区间,问最后纸条上的颜色情 况。(纸条长度L,涂色次数N) 朴素算法:O(L×N) 线段树:O(ogL×N) 后继数组:O(L+N)

后继数组(1) ▪ 问题:给一个纸条涂色,每次用某种颜色 涂某个连续区间,问最后纸条上的颜色情 况。(纸条长度L,涂色次数N) ▪ 朴素算法:O( L×N ) ▪ 线段树:O( logL×N ) ▪ 后继数组:O( L+N )

后继数组(2) 反向处理 加开一个一维数组,记录下一个未涂色点的位置 (NO冬令营2005朱泽园) 012845678901213 12|311999911118 7,11绿色

后继数组(2) ▪ 反向处理 ▪ 加开一个一维数组,记录下一个未涂色点的位置 ▪ (NOI冬令营2005 朱泽园) 1 2 3 4 5 6 7 8 9 10 11 12 13 14 × [5,8] 蓝色 9 9 9 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 [3,10] 红色 11 11 11 11 [7,11] 绿色 12

动态规划 神伏化模式

动态规划 两种优化模式

共25页,试读已结束,阅读完整版请下载
刷新页面下载完整文档
VIP每日下载上限内不扣除下载券和下载次数;
按次数下载不扣除下载券;
注册用户24小时内重复下载只扣除一次;
顺序:VIP每日次数-->可用次数-->下载券;
相关文档