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

Re: [問題] LeetCode 378. Kth Smallest Element...

看板Prob_Solve (計算數學 Problem Solving)作者alan23273850時間7年前 (2017/08/07 13:34)推噓1(1推 0噓 5→)

留言6則, 2人參與討論串3/3 (看更多)

我們演算法老師說過對於一些比較常用、有名的算法，通常已經有先人發展出漂亮的寫法我們的任務就是找出漂亮、優美的寫法，理解它，然後背起來！雖然老師那個時候是拿 qsort 當例子，但是我想 binary search 也是一樣的。這是我去年複習的時候寫的投影片中的其中一頁： https://upload.cc/i1/2020/05/09/927SNu.jpg

我是覺得這樣的寫法還是比較好理解至於遇到多重相同值元素時可以一直往前找，就能碰到第一個出現的元素，相對地如果要最後一個元素就一直往後找就好！另外，我自己是感覺這種著名算法未必要很堅持的看懂其他人的寫法，因為這種小細節往往是會花最多時間的地方，其實只要自己會寫、寫得出來就好。當然能快速看懂一個人的 code 是種超能力，但如果是為了訓練這種能力而花時間在這種小細節上，CP 值恐怕不高。(花太多時間，卻只提升一點點能力) -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.168.85.29 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1502084077.A.70A.html ※ 編輯: alan23273850 (1.168.85.29), 08/07/2017 19:58:12

→

FRAXIS

08/07 21:27, , 1^F

08/07 21:27, 1^F

謝謝F大的提醒！！！這篇真是獻醜了，我還真的沒想過這樣會讓複雜度變成 O(n)，想說學校這樣教、我就這樣理解，果然人還是有盲點的。剛剛稍微分析了一下，假設把最後線性查找的部分再改為二次 binary search，那複雜度變成 lgn + lg(n/2) + lg(n/4) + lg(n/8) + ...... = lgn + (lgn-1) + (lgn-2) + (lgn-3) + ...... = lgn + klgn - k(k+1)/2 // 然後假設最多重複查找 k = lgn 次 = lgn + lgnlgn - 0.5lgn(lgn+1) = 0.5(lgnlgn + lgn) 如此一來，雖然比原生的 lgn 要慢，但是還是比一律線性查找的 O(n) 要快得多 ----------------------------------------------------------------------- 至於原 PO 所提到何時 high=mid、何時 high=mid-1 的問題，我認為就是搭配 while 迴圈來看，只要確保每次迭代都至少能減少一個 problem size 為原則即可。我有時間再來詳細看看新版本的 binary search 要怎麼理解比較好，寫成新的投影片之後再貼上來。 https://stackoverflow.com/questions/6443569/implementation-of-c-lower-bound (最下面的 code 是本次重點) 而這篇文有警惕意味，所以會留著不會刪文。 ※ 編輯: alan23273850 (1.168.85.29), 08/07/2017 23:29:17