作者netsphere (再一次重来...)
看板Prob_Solve
标题[问题] LIS的lower bound
时间Thu Oct 9 17:40:18 2008
最近因为专题在研究LIS的演算法
LIS的介绍:
http://www.csie.ntnu.edu.tw/~u91029/LongestIncreasingSubsequence.html
用DP , Greedy method , graph 解决 我大致都了解了
现在我想要找出 LIS 问题的 Lower bound 可是没有什麽头绪....
我知道是O(nlogn) 但不知道为什麽 .... google也没找到什麽东西 Orz
有大大可以给个 方向 或 相关资料 吗?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 163.22.18.90
※ 编辑: netsphere 来自: 163.22.18.90 (10/09 18:20)
1F：推 flyakite:at least scan once(n) and a binary search (㏒n) 10/10 11:48
2F：→ netsphere:恩 谢谢 但这是基於greedy method的分析 10/10 14:02
3F：→ netsphere:我想要证明的是像 基於比较的sort最低下限是O(nlogn) 10/10 14:03
4F：→ xcycl:lower bound 叫做 Ω 10/11 18:58
5F：→ netsphere:恩 是应该叫Ω 10/11 20:22