9512.net
甜梦文库
当前位置:首页 >> 学科竞赛 >>

导弹拦截nlogn算法



拦截导弹
? 给定N个数
– 求最长的不上升子序列长度 – 求最少有多少个不上升序列能覆盖所有的数, 即求最少覆盖序列。

? N<=10000.

分析
? 设f(i)表示前i个数的最长不上升序列的长度。 则, f(i)=max{f(j)+1},其中j<i and a[j]>=a[i] 这

里0<j<i<=n。 显然时间复杂度为O(n2)。 ? 上述式子的含义:找到i之前的某j,这个数 不比第i个数小,对于所有的j取f(j)的最大值。

优化
? 分析样例 i f 1 2 3 4 5 6 7 8 389 207 155 300 299 170 158 65 1 2 3 2 3 4 5 6

? 这里找j,是在1~i之间进行寻找,那么我们能否快速查找到 我们所要更改的j呢? ? 要能更改需要两个条件: – j<i and a[j]>=a[i] – f(j)尽可能大 ? 以上两个条件提示我们后面的值一定要小于等于前面的值。 因此我们试着构建一个下降的序列。在这个下降的序列中 查找可以更改的f值,使得序列的值尽可能大。

? 具体过程:
i 1 2 3 4 5 6 7 8

389
第 1次 第 2次 389 389

207

155

300

299

170

158

65

207

第 3次
第 4次 第 5次 第 6次 第 7次 第 8次

389
389 389 389 389 389

207
300 300 300 300 300

155
155 299 299 299 299 (由于207<300<389,因此更新) (由于155<299<300,因此更新) 170 170 170 158 158 65

思考?
? 有些同学可能会问: – 对于每个f,为什么只保留一个数值呢? – 而对于该序列,为什么要保留较大的值呢? 1. 再回过头来看方程: f(i)=max{f(j)+1},其中j<i and a[j]>=a[i] 该式子表示找前面的一个最大f的符合条件的j,因此只要保 存符合条件的最大的j就可以了。 2. 在f值相同的情况下,保留较大的数显然更好。因为后面 的数若能跟较小的数构成下降序列也一定能能较大的数 构成下降序列,反之则不一定。例如207与300的f=2,但 207不能与299构成下降序列,而300则可以。
3. 因为生成的序列为有序序列,因此我们可以采用二分查 找的方法很快查找到更新的值,时间复杂度为O(n㏒n)

求导弹的最小覆盖
? 第二问很容易想到贪心法:那就是采取多次求最 长不上升序列的办法,然后得出总次数。 ? 上述贪心法不正确,很容易就能举出反例。 例如: “7 5 4 1 6 3 2” 用多次求最长不上升序列所有为 “7 5 4 3 2”、“1”、“6”共3套系统; 但其实只要2套,分别为: “7 5 4 1”与“6 3 2”。 ? 那么,正确的做法又是什么呢?

分析
? 上述问题的原因是若干次最优决策值和不 一定能推导出整个问题的最优。 ? 为了解决这个问题下面介绍一个重要性质:
– 最少链划分=最长反链长度

? 为了证明这个性质,需要了解离散数学中 偏序集的相关概念和性质以及偏序集的 Dilworth定理。

偏序集
? 偏序是在集合X上的二元关系≤(这只是个抽象符号,不是 “小于或等于”),它满足自反性、反对称性和传递性。 即,对于X中的任意元素a,b和c,有:
– 自反性:a≤a; – 反对称性:如果a≤b且b≤a,则有a=b; – 传递性:如果a≤b且b≤c,则a≤c 。

? 带有偏序关系的集合称为偏序集。 ? 令(X,≤)是一个偏序集,对于集合中的两个元素a、b,如果 有a≤b或者b≤a,则称a和b是可比的,否则a和b不可比。 ? 一个反链A是X的一个子集,它的任意两个元素都不能进 行比较。 ? 一个链C是X的一个子集,它的任意两个元素都可比。

定理
? 在X中,对于元素a,如果任意元素b,都有a≤b, 则称a为极小元。 ? 定理1:令(X,≤)是一个有限偏序集,并令r是其 最大链的大小。则X可以被划分成r个但不能再少 的反链。 ? 其对偶定理称为Dilworth定理: 令(X,≤)是一个有限偏序集,并令m是反链的最 大的大小。则X可以被划分成m个但不能再少的链。

? 虽然这两个定理内容相似,但第一个定理证明要 简单一些。此处就只证明定理1。

证明:设p为最少反链个数 (1)先证明X不能划分成小于r个反链。由于r是最大 链C的大小,C中任两个元素都可比,因此C中任 两个元素都不能属于同一反链。所以p>=r。 (2)设X1=X,A1是X1中的极小元的集合。从X1中删 除A1得到X2。注意到对于X2中任意元素a2,必存 在X1中的元素a1,使得a1<=a2。令A2是X2中极小 元的集合,从X2中删除A2得到X3……,最终会有 一个Xk非空而Xk+1为空。于是A1,A2,…,Ak就是X的 反链的划分,同时存在链a1<=a2<=…<=ak,其中ai 在Ai内。由于r是最长链大小,因此r>=k。由于X 被划分成了k个反链,因此r>=k>=p。 (3)因此r=p,定理1得证。

解决
? 要求最少的覆盖,按照Dilworth定理 ? 最少链划分 = 最长反链长度 所以最少多少套系统 = 最长导弹高度上升 序列长度。
? 知道了怎样求最长不上升算法,同样也就 知道了怎样求最长上升序列。 ? 时间复杂度O(n㏒n)。



更多相关文章:
lis算法详解
可以使用二分查找高效 地完成,则整个算法时间复杂度下降为 O(nlogn),有了非常...[i] = j; } return size; } 题目分析:同 NYOJ 79 拦截导弹 先解释下...
算法练习题
算法练习题_电脑基础知识_IT/计算机_专业资料。一、判断题 1-1 算法分析的两...(4 分) A、N^2logNN B、N(logN)^4 C、N^3 D、NlogN^2 2-2 给定 ...
在最好和最坏情况下的时间复杂度均为O(nlogn),但不稳定...
在最好和最坏情况下的时间复杂度均为O(nlogn),但不稳定的排序算法是()。 A.堆排序 B.快速排序 C.归并排序 D.基数排序_答案解析_2016年_一模/二模/三模/...
算法11年期末考试卷答案
3. (× )快速排序算法的平均时间复杂度是 O(nlogn),使用随机化快速排 序算法可以将平均时间复杂度降得更低。 4. (× )如果一个问题是 NP 问题,则它一定...
算法设计与分析复习要点
贪心算法只有在具有贪心选择性质时才能保证获得整体最优。 Prim 算法(O(n2)):在连通的情况下选择权值较小的边。 Kruskal 算法(O(nlogn)):在无回路情况下选择...
《数据结构》第08章在线测试
A、希尔排序 B、冒泡排序 C、快速排序 B、选择排序 D、起泡排序 D、直接插入排序 2、下列方法中,___算法的时间复杂度为 O(nlogn)。 A、直接插入排序 B、...
算法分析与设计-贪心算法
算法分析与设计-贪心算法_计算机软件及应用_IT/计算机_专业资料。专业课程实验报告...WHILE 循环中其他的操作都是常数级别的, 所以整个 WHILE 循环就是 O(nlogn)。...
第八单元 简单算法时空分析
第八单元 简单算法时空分析 8.1 算法分析的概念算法分析是指通过数学方法对一...(nloglogn) < O(nlogn) < O(n^2) O(n^2) < O(n^3) < O(2^n)...
算法分析的原理
这种情况对于一个必须处理 N 个输入(或产生 N 个输出)的算法是最 优的。 NlogN 当把问题分解成小问题,且独立求解只问题,然后把这些子问题好 的解组合成原有...
算法分析与设计考试样卷
则 于是 即 T(n) = O(nlogn) 总结,利用此方法解递归算法复杂度: f(n) = af(n/b) + d(n) 1.当 d(n)为常数时: 2.当 d(n) = cn 时: 3....
更多相关标签:
算法训练 拦截导弹    nlogn 算法    排序算法nlogn    导弹拦截    弹道导弹为什么难拦截    洲际导弹无法拦截    洲际导弹可以拦截吗    萨德能拦截中国导弹吗    

All rights reserved Powered by 甜梦文库 9512.net

copyright ©right 2010-2021。
甜梦文库内容来自网络,如有侵犯请联系客服。zhit325@126.com|网站地图