[問題] LIS的lower bound

[netsphere (再一次重來...)]

最近因為專題在研究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)
推 flyakite:at least scan once(n) and a binary search (㏒n)
→ netsphere:恩 謝謝  但這是基於greedy method的分析
→ netsphere:我想要證明的是像 基於比較的sort最低下限是O(nlogn)
→ xcycl:lower bound 叫做 Ω
→ netsphere:恩 是應該叫Ω