算优化
算法优化 贾由
为什么先讲算法优化? 算法优化不是高级算法 算法优化是关于算法的思维方式 化孤立为体系
为什么先讲算法优化？ ▪ 算法优化不是高级算法 ▪ 算法优化是关于算法的思维方式 ▪ 化孤立为体系
主要意图 ■提供一些有普遍性、有启发性的优化模式 从一个已有算法,大概知道可以从哪些方 面着手提高它的性能
主要意图 ▪ 提供一些有普遍性、有启发性的优化模式 ▪ 从一个已有算法，大概知道可以从哪些方 面着手提高它的性能
内容框架 数据结构与优化 动态规划的优化 搜索的优化 贪心与优化
内容框架 ▪ 数据结构与优化 ▪ 动态规划的优化 ▪ 搜索的优化 ▪ 贪心与优化
数推施判 两个启发小夹倒
数据结构 两个启发性实例
块状链表(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
动态规划 神伏化模式
动态规划 两种优化模式