※ 引述《ephesians (ephesians)》之銘言：
: ※ 引述《march20 ()》之銘言：
: (前面的平地球model無濟於事,所以省略)
: : 回到原來的 case. 一般來說, 我們常用的資料型別就足以處理大部份問題了, 在這情況
: : 下, 我們把 memory access 當成是 O(1), 對這些資料作四則運算, 或是作有效位數內的
: : shift 都可以看成是 constant time. 今天遇到的問題有可能會 shift(100),
: : shift(200), 甚或是 shift(10^10), 這時候再說 shift 是 constant time 就沒道理
: : 了. (如果這樣也可以當 constant time 來講, 那以後演算法都不用教 bignum 好了 XD)
: 講了半天仍然內定 shift(n) = shft(n-1) + shift 1,
: 但我就是質疑,shift計算真的是上述式子嗎?
: 在上述式子中,你所講的shift當然是循序的.
: 但問題是我就是要拆你的台,我所談的並不是基於上述數學式子,
: 而是以別的計算方式為主,譬如 sfift(n) = (A & B) | (C & D)
呃, 不管你要用什麼邏輯式子, &, +, -, *, % 組成的式子, 原來 operand 是多少 bit
最糟情況結果至少就是那麼多 bit. 所以如果 n 夠大, 計算量還是會變大的.
(除非你做 f(n) = n - n 這種事 XD)
: 我算shirt(1)是這個邏輯式子,算shift(2000)照樣是這個邏輯式子,
: 並沒有因為n變得多大,式子的計算量就變大.
: 軟體層面,你假定一個數學計算model沒問題.
: 但RAM它是硬體,請不要用軟體的思維去假想它是怎麼運作的.
: 也許硬體中真的就是O(1),卻被不知硬體的人假想為軟體的加加減減,
這個, 能不能給個, 不論 A, B 多大, A << B 都是 constant time 的 CPU 給我,
我來去買一個 XD
: 那這樣子random access這個名字變得沒有意義了,
: 就像前前文隨意講的一句話:
: "(RAM model書上的解釋)巧妙地躲開定址所需要的O(logn)問題"
: 這話有什麼根據?
: 你可以這樣假想,但這假想的東西跟硬體實際情況相衝的時候,
: 我就可以覺得你講得荒謬,而要你提出具體說明.
對, 你得到他了, 當一個 model 在某個 case 跟實際情況差太多時我們就不該用他,
這就是為什麼在這裡我們不能繼續把 shift 當成 O(1) 的原因,
因為跟硬體實際情況衝突了
: 萬一它不是呢? 這時候你可能又說,反正只是我的model,與實際情況不合沒關係.
: 但問題是,因為那句未經證實的話,
: 許多人可能會被誤導,而開始思考 a[65535] = 65 這一行程式是O(1)還是O(n)!!!
: 這很可怕啊!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 71.136.243.18
※ 編輯: march20 來自: 71.136.243.18 (06/23 01:37)