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

Re: [問題] ancestry problem

看板Prob_Solve (計算數學 Problem Solving)作者march20時間17年前 (2007/06/22 16:20)推噓1(1推 0噓 0→)

留言1則, 1人參與討論串10/15 (看更多)

: 推 ephesians:確定嗎?既然是硬體,為什麼不是組合邏輯運算,而是loop? 06/22 12:15 : → ephesians:硬體上,shift n是多個運算,或是一個運算? 06/22 12:18 : 推 jeunder:抗議! 為何 address 的 O(logn) 加法就可以視為 O(1) ? 06/22 12:28 : → jeunder:為何 node 編號的 O(logn) shift 就要視為 O(logn) ? 06/22 12:29 : 推 ephesians:這樣想起來很可怕,以後要算時間複雜度可麻煩了, 06/22 13:05 : → ephesians:要從基本邏輯計算開始一條條算 06/22 13:05 : 推 ledia:shift logn 可以很大呀, 不一定是一次 inst. 就做得出來的 06/22 13:16 : → ledia:而且你要比較演算法本來就需要在公同 model 上 06/22 13:17 : → ledia:定什麼樣的 model 只是讓大家方便吧想要不一樣的也行呀 06/22 13:17 : → ledia:如果你們不能接受我的說法去看書的解釋吧 :p 06/22 13:18 : 推 march20:別的不說, 光 shift 100, 200 就不是一般處理器能一次做的 06/22 13:17 : 推 ephesians:你的說法是來自於書上? 06/22 13:24 : 推 ledia:我的文章.... 有這麼難看懂嗎? 第一句? @@? 06/22 13:31 : → ledia:還是你直接跳過第一段? XD 06/22 13:31 : 推 ephesians:但你後面的解釋也是從書裡來的?(我的問題有那麼難懂嗎?) 06/22 13:41 : → ephesians:我是指你將他曲解為巧妙躲開的那句 06/22 13:45 : 推 ledia:你還沒看到書上說什麼就說我曲解是不是不很恰當呢? 06/22 13:52 : → ledia:巧妙的躲開的確是我自己的說法, 因為這是避免演算法分析 06/22 13:53 : → ledia:還要牽扯太多複雜的 addressing 的問題的緣故 06/22 13:54 : 推 ledia:既然你今天討論的是演算法問題, 本來就需要個基準點 06/22 13:56 : 推 ephesians:我並沒下定論,但也該表達我的質疑 06/22 15:10 : → ephesians:另外我不認為基準點可以一下子高層一下子低層 06/22 15:11 http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK/NODE12.HTM 這裡有一段說得很好: Every model has a size range over which it is useful. Take, for example, the model that the earth is flat. You might argue that this is a bad model, since the earth is not flat. However, when laying the foundation of a house, the flat earth model is sufficiently accurate that it can be reliably used. Further, it is so much easier to manipulate a flat-earth model that it is inconceivable that you would try to think spherically when you don't have to. 並不是說基準點可以一下高一下低. 就像在討論量子力學時, 你還要拿古典力學來當基準, 那保證是拿石頭砸自己腳. 同樣的, 在討論古典力學時, 偏偏要計入相對可以忽略的強作用力弱作用力, 那根本是沒事找事做. 回到原來的 case. 一般來說, 我們常用的資料型別就足以處理大部份問題了, 在這情況下, 我們把 memory access 當成是 O(1), 對這些資料作四則運算, 或是作有效位數內的 shift 都可以看成是 constant time. 今天遇到的問題有可能會 shift(100), shift(200), 甚或是 shift(10^10), 這時候再說 shift 是 constant time 就沒道理了. (如果這樣也可以當 constant time 來講, 那以後演算法都不用教 bignum 好了 XD) -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 71.136.243.18 ※ 編輯: march20 來自: 71.136.243.18 (06/22 16:20) ※ 編輯: march20 來自: 71.136.243.18 (06/22 16:21)