[关闭]
@Pigmon 2016-04-29T06:14:49.000000Z 字数 1141 阅读 134

算法作业 _ 7_袁胜_2016M8009073008

Python


基本思路

通过题目中原图,构造如下字典用于记录待考察的相容线段集合:
Key: 序号
Value: 候选的相容线段集合列表。
构造完成后,选取其中最长的候选线段集合,即为所求的最大相容线段集合。
此处输入图片的描述

添加新候选列表的条件

将新线段插入当前存在 List 末尾的条件

因为题目中的相交条件是,或者,所以,如果在新线段new左侧找到一条相容线段l,则l 左侧所有与 l 相容的线段,皆与新线段 new 相容。即该子问题求解满足动态规划法需求中的无后效性。

这样经过[1..n]的1次循环考察,就构建了上图所示的 Dict,从中可以找出题目的最大相容线段集合。

伪码

  1. Algorithm MaxNoCross(A[]):
  2. n <- Lenght(A);
  3. Dict <- 存储所有候选 List 的字典;
  4. for (i in 0..n-1):
  5. if Cross(All line in Dict, A[i]) || Dict.Empty():
  6. Dict.Add(new List(A[i]));
  7. else:
  8. Guard <- False; // 监视是否有直接可插入的 List
  9. foreach List in Dict:
  10. if !Cross(List末尾线段, A[i]):
  11. List.Append(A[i]);
  12. Guard <- True;
  13. end
  14. end
  15. if !Guard:
  16. l <- 位于A[i]左侧,且距离A[i]最近的不相交线段
  17. foreach List in Dict:
  18. if List.Contains(l):
  19. Dict.Add(List[0..l,A[i]]);
  20. end
  21. end
  22. end
  23. end
  24. end
  25. return LongestList(Dict);
  26. end

时间复杂度分析

最坏情况,即每次考察新线段,当前 Dict 中所有线段与新线段皆相交。这样每次都要对比一遍目前已考察的所有线段。
令一次比较2线段是否相交的时间复杂度为 ,则最坏情况下时间复杂度


即最坏情况下时间复杂度为

添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注