作者ephesians (ephesians)
看板Prob_Solve
標題Re: [問題] ancestry problem
時間Fri Jun 22 17:30:55 2007
※ 引述《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)
我算shirt(1)是這個邏輯式子,算shift(2000)照樣是這個邏輯式子,
並沒有因為n變得多大,式子的計算量就變大.
軟體層面,你假定一個數學計算model沒問題.
但RAM它是硬體,請不要用軟體的思維去假想它是怎麼運作的.
也許硬體中真的就是O(1),卻被不知硬體的人假想為軟體的加加減減,
那這樣子random access這個名字變得沒有意義了,
就像前前文隨意講的一句話:
"(RAM model書上的解釋)巧妙地躲開定址所需要的O(logn)問題"
這話有什麼根據?
你可以這樣假想,但這假想的東西跟硬體實際情況相衝的時候,
我就可以覺得你講得荒謬,而要你提出具體說明.
萬一它不是呢? 這時候你可能又說,反正只是我的model,與實際情況不合沒關係.
但問題是,因為那句未經證實的話,
許多人可能會被誤導,而開始思考 a[65535] = 65 這一行程式是O(1)還是O(n)!!!
這很可怕啊!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.160.114.106
1F：→ ledia:RAM model 不是硬體 是 model ... 可以去看一下書嗎? XD 06/22 17:32
2F：→ ledia:我是不知道為什麼你這麼愛現在硬體能做到什麼扯上關係 06/22 17:32
3F：→ ledia:也許是你以為這裡的 RAM 是 random-access memory 06/22 17:32
4F：→ ledia:但是這是演算法在比較時所需要的一個基準點 06/22 17:33
5F：→ ledia:定好哪些東西是 unit cost, 哪些不是 06/22 17:33
6F：→ ledia:這樣演算法才能互相比較 06/22 17:34
7F：→ ledia:如果真的要講硬體 shift(2000) 和 shift(1) 的 2000,1 06/22 17:34
8F：→ ledia:bit 數也不會一樣呀 06/22 17:35
9F：→ ledia:也就是你的 A, B, C, D 的 bit 數並不相同 06/22 17:35
10F：→ ledia:如此失焦下去, 什麼時候才能開始討論演算法呢? 06/22 17:35
11F：推 ledia:最後... 我想講到這你再不同意 我也掰不出別的了 06/22 17:39
12F：→ ledia:所以我就此打住 也讓板主方便 ^^: 06/22 17:39
13F：推 ephesians:我講的是random access memory 06/22 17:57
14F：→ ephesians:你還可以回答我a[65535]是一個動作還是65535個動作? 06/22 17:57
15F：→ ephesians:A,B,C,D是隨便舉例的,你還真的討論bit數,我昏了 06/22 17:59