討論串[問題] ancestry problem
共 15 篇文章
內容預覽:
啊, 來回覆原 po XD. 一聽到這個題目, 印象中有個 disjoint set 相關的 data structure/algorithm. 然後 time complexity 是 inverse Akerman function (可以當作 O(1) 來看).. 一查果然有這題.. 如果你手
(還有64個字)
內容預覽:
(前面的平地球model無濟於事,所以省略). 講了半天仍然內定 shift(n) = shft(n-1) + shift 1,. 但我就是質疑,shift計算真的是上述式子嗎?. 在上述式子中,你所講的shift當然是循序的.. 但問題是我就是要拆你的台,我所談的並不是基於上述數學式子,. 而是以
(還有361個字)
內容預覽:
呃, 不管你要用什麼邏輯式子, &, +, -, *, % 組成的式子, 原來 operand 是多少 bit. 最糟情況結果至少就是那麼多 bit. 所以如果 n 夠大, 計算量還是會變大的.. (除非你做 f(n) = n - n 這種事 XD). 這個, 能不能給個, 不論 A, B 多大,
(還有104個字)
內容預覽:
我有一個想法耶. 先對那棵tree做一次DFS. 並紀錄每一點的進入和離開時間. 進入時間指的是從parent走到它的時間. 離開時間指的是從它走回parent的時間. 以右圖為例 Ａ. ／＼. DFS順序： ABDBEBACA Ｂ Ｃ. ／＼. 時間 A B C D E Ｄ Ｅ. 進(t1) 1
(還有21個字)
內容預覽:
我在看這篇文章的時候,完全同意大大的說法. 可是在我看mit press(introduction to algorithms). 裡面chapter2的p 22裡面提到. many computers have a "shift left" instruction , which. in cons
(還有123個字)