Re: [問題] ancestry problem

[ledia ()]

※ 引述《jeunder ()》之銘言：
: ※ 引述《march20 ()》之銘言：
: : 對整數 shift n bits 確實是 O(1), 但如果這顆樹的高度是 100, 200,
: : (一代單傳的樹, 然後傳 100 或 200 代就是了, 並不難造 XD)
: :  或怎更多時, 鐵定不是 O(1) 可以完成的 XD
: 所以說在沒有對 array 做 preprocessing (例如: sorting...) 的情況下
: 要在 array 裡面 search 某個東西... 是 O(nlogn) 囉? XD
: 怎麼說? 因為對 array 裡面的項目定址需要用到 O(logn) 個 bits,
: 而依序 search n 個項目, 每次都要對位址做 O(logn) bits 的加法,
: 所以 array search 是 O(nlogn) ?
: 按照你的說法, 如果 array 裡面的元素數量是一兆, 兩兆或更多時,
: 位址的運算鐵定不是 O(1) 可以完成的 XD
  這也就是為什麼很多 complexity/algorithm 的書籍
  開宗明義會先說清楚他們在什麼 model 上討論問題
  像是許多書用的就是 random access machine (RAM) model

  RAM model 的其中一個條件就是

  * Each memory access takes exactly one time step, and we have as
  much memory as we need. The RAM model takes no notice of whether
  an item is in cache or on the disk, which simplifies the analysis.

  巧妙的躲開了定址所需要的 O(logn) 的問題

  但是 shift logn bits 仍然是用 loop 做出來的
  則應該還是需要花 O(logn) 的時間

--

  有時候，遺忘，是令人快樂的。什麼時候？當然是有人傷了你的心的時候。
　存心傷你的那個人，固然是故意和你過不去，但是被傷了心而耿耿於懷的你
　，卻是和自己過不去了。所以，記性不好的人，通常會是比較快樂的人，也
　是比較不容易被擊倒的人。

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.56
※ 編輯: ledia           來自: 140.112.30.56        (06/22 09:50)
推 ephesians:確定嗎?既然是硬體,為什麼不是組合邏輯運算,而是loop?
→ ephesians:硬體上,shift n是多個運算,或是一個運算?
推 jeunder:抗議! 為何 address 的 O(logn) 加法就可以視為 O(1) ?
→ jeunder:為何 node 編號的 O(logn) shift 就要視為 O(logn) ?
推 ephesians:這樣想起來很可怕,以後要算時間複雜度可麻煩了,
→ ephesians:要從基本邏輯計算開始一條條算
推 ledia:shift logn 可以很大呀, 不一定是一次 inst. 就做得出來的
→ ledia:而且你要比較演算法 本來就需要在公同 model 上
→ ledia:定什麼樣的 model 只是讓大家方便吧 想要不一樣的也行呀
→ ledia:如果你們不能接受我的說法 去看書的解釋吧 :p
推 march20:別的不說, 光 shift 100, 200 就不是一般處理器能一次做的
推 ephesians:你的說法是來自於書上?
推 ledia:我的文章.... 有這麼難看懂嗎? 第一句? @@?
→ ledia:還是你直接跳過第一段? XD
推 ephesians:但你後面的解釋也是從書裡來的?(我的問題有那麼難懂嗎?)
→ ephesians:我是指你將他曲解為巧妙躲開的那句
推 ledia:你還沒看到書上說什麼 就說我曲解是不是不很恰當呢?
→ ledia:巧妙的躲開的確是我自己的說法, 因為這是避免演算法分析
→ ledia:還要牽扯太多複雜的 addressing 的問題的緣故
推 ledia:既然你今天討論的是演算法問題, 本來就需要個基準點
推 ephesians:我並沒下定論,但也該表達我的質疑
→ ephesians:另外我不認為基準點可以一下子高層一下子低層
推 ledia:我今天學到意指別人屈解不是下定論
→ ledia:不過我一點沒有想要說服你, 你覺得不該怎樣, 請繼續如此想
推 ephesians:要人認為你不是曲解,給個證明!
→ ephesians:要講RAM仍是循序運算,你可以列個layout指出它哪裡循序
→ ephesians:你說不說服我根本不重要,重要的是講你錯的地方你能不能
→ ephesians:證明你沒有錯?
推 ledia:是你在曲解 是你應該要提證明吧 XD
→ ledia:你能不能證明你沒有錯?
→ ledia:march 也把我看的書的出處也點出來了
→ ledia:你如果還想要在這裡打轉 你自便吧 :p