PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] LIS的lower bound

看板Prob_Solve (計算數學 Problem Solving)作者 (再一次重來...)時間16年前 (2008/10/09 17:40), 編輯推噓1(1推 0噓 4→)
留言5則, 3人參與, 最新討論串1/1
最近因為專題在研究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)
推
10/10 11:48, , 1F
at least scan once(n) and a binary search (㏒n)
10/10 11:48, 1F
→
10/10 14:02, , 2F
恩 謝謝 但這是基於greedy method的分析
10/10 14:02, 2F
→
10/10 14:03, , 3F
我想要證明的是像 基於比較的sort最低下限是O(nlogn)
10/10 14:03, 3F
→
10/11 18:58, , 4F
lower bound 叫做 Ω
10/11 18:58, 4F
→
10/11 20:22, , 5F
恩 是應該叫Ω
10/11 20:22, 5F
‣ 更多 netsphere 的文章
文章代碼(AID): #18xT67Bk (Prob_Solve)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 netsphere 的文章
文章代碼(AID): #18xT67Bk (Prob_Solve)