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

Re: [問題] ancestry problem

看板Prob_Solve (計算數學 Problem Solving)作者時間17年前 (2007/06/22 09:50), 編輯推噓14(14推 0噓 18→)
留言32則, 4人參與, 最新討論串9/15 (看更多)
※ 引述《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)
推
06/22 12:15, , 1F
確定嗎?既然是硬體,為什麼不是組合邏輯運算,而是loop?
06/22 12:15, 1F
→
06/22 12:18, , 2F
硬體上,shift n是多個運算,或是一個運算?
06/22 12:18, 2F
推
06/22 12:28, , 3F
抗議! 為何 address 的 O(logn) 加法就可以視為 O(1) ?
06/22 12:28, 3F
→
06/22 12:29, , 4F
為何 node 編號的 O(logn) shift 就要視為 O(logn) ?
06/22 12:29, 4F
推
06/22 13:05, , 5F
這樣想起來很可怕,以後要算時間複雜度可麻煩了,
06/22 13:05, 5F
→
06/22 13:05, , 6F
要從基本邏輯計算開始一條條算
06/22 13:05, 6F
推
06/22 13:16, , 7F
shift logn 可以很大呀, 不一定是一次 inst. 就做得出來的
06/22 13:16, 7F
→
06/22 13:17, , 8F
而且你要比較演算法 本來就需要在公同 model 上
06/22 13:17, 8F
→
06/22 13:17, , 9F
定什麼樣的 model 只是讓大家方便吧 想要不一樣的也行呀
06/22 13:17, 9F
→
06/22 13:18, , 10F
如果你們不能接受我的說法 去看書的解釋吧 :p
06/22 13:18, 10F
推
06/22 13:17, , 11F
別的不說, 光 shift 100, 200 就不是一般處理器能一次做的
06/22 13:17, 11F
推
06/22 13:24, , 12F
你的說法是來自於書上?
06/22 13:24, 12F
推
06/22 13:31, , 13F
我的文章.... 有這麼難看懂嗎? 第一句? @@?
06/22 13:31, 13F
→
06/22 13:31, , 14F
還是你直接跳過第一段? XD
06/22 13:31, 14F
推
06/22 13:41, , 15F
但你後面的解釋也是從書裡來的?(我的問題有那麼難懂嗎?)
06/22 13:41, 15F
→
06/22 13:45, , 16F
我是指你將他曲解為巧妙躲開的那句
06/22 13:45, 16F
推
06/22 13:52, , 17F
你還沒看到書上說什麼 就說我曲解是不是不很恰當呢?
06/22 13:52, 17F
→
06/22 13:53, , 18F
巧妙的躲開的確是我自己的說法, 因為這是避免演算法分析
06/22 13:53, 18F
→
06/22 13:54, , 19F
還要牽扯太多複雜的 addressing 的問題的緣故
06/22 13:54, 19F
推
06/22 13:56, , 20F
既然你今天討論的是演算法問題, 本來就需要個基準點
06/22 13:56, 20F
推
06/22 15:10, , 21F
我並沒下定論,但也該表達我的質疑
06/22 15:10, 21F
→
06/22 15:11, , 22F
另外我不認為基準點可以一下子高層一下子低層
06/22 15:11, 22F
推
06/22 16:18, , 23F
我今天學到意指別人屈解不是下定論
06/22 16:18, 23F
→
06/22 16:19, , 24F
不過我一點沒有想要說服你, 你覺得不該怎樣, 請繼續如此想
06/22 16:19, 24F
推
06/22 17:06, , 25F
要人認為你不是曲解,給個證明!
06/22 17:06, 25F
→
06/22 17:07, , 26F
要講RAM仍是循序運算,你可以列個layout指出它哪裡循序
06/22 17:07, 26F
→
06/22 17:08, , 27F
你說不說服我根本不重要,重要的是講你錯的地方你能不能
06/22 17:08, 27F
→
06/22 17:09, , 28F
證明你沒有錯?
06/22 17:09, 28F
推
06/22 17:29, , 29F
是你在曲解 是你應該要提證明吧 XD
06/22 17:29, 29F
→
06/22 17:29, , 30F
你能不能證明你沒有錯?
06/22 17:29, 30F
→
06/22 17:30, , 31F
march 也把我看的書的出處也點出來了
06/22 17:30, 31F
→
06/22 17:30, , 32F
你如果還想要在這裡打轉 你自便吧 :p
06/22 17:30, 32F
‣ 更多 ledia 的文章
文章代碼(AID): #16UohPJF (Prob_Solve)
討論串 (同標題文章)
本文引述了以下文章的的內容：
以下文章回應了本文 (最舊先)：
完整討論串 (本文為第 9 之 15 篇)：
排序： 最舊先 | 最新先 | 留言數
在新視窗開啟完整討論串 (共15篇)
Prob_Solve 近期熱門文章
更多 近期熱門文章 >>
PTT數位生活區 即時熱門文章
更多 即時熱門文章 >>
‣ 更多 ledia 的文章
文章代碼(AID): #16UohPJF (Prob_Solve)