算法优化.ppt.ppt

文档介绍：算法优化
贾由
为什么先讲算法优化?
算法优化不是高级算法
算法优化是关于算法的思维方式
化孤立为体系
主要意图
提供一些有普遍性、有启发性的优化模式
从一个已有算法,大概知道可以从哪些方面着手提高它的性能
内容框架
数据结构与优化
动态规划的优化
搜索的优化
贪心与优化
数据结构
两个启发性实例
块状链表(1)
向量
定位O(1),增删O(n)
链表
定位O(n),增删O(1)
块状链表
定位O(n1/2),增删O(n1/2)
块状链表(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( logL×N )
后继数组:O( L+N )
后继数组(2)
反向处理
加开一个一维数组,记录下一个未涂色点的位置
(NOI冬令营2005 朱泽园)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
×
[5,8] 蓝色
9
9
9
9
1
2
3
4
5
6
7
8
9
10
11
12
13
14
0
[3,10] 红色
11
11
11
11
[7,11] 绿色
12
动态规划
两种优化模式