Re: [問題] ancestry problem

[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)
我算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
→ ledia:RAM model 不是硬體 是 model ... 可以去看一下書嗎? XD
→ ledia:我是不知道為什麼你這麼愛現在硬體能做到什麼扯上關係
→ ledia:也許是你以為這裡的 RAM 是 random-access memory
→ ledia:但是這是演算法在比較時所需要的一個基準點
→ ledia:定好哪些東西是 unit cost, 哪些不是
→ ledia:這樣演算法才能互相比較
→ ledia:如果真的要講硬體 shift(2000) 和 shift(1) 的 2000,1
→ ledia:bit 數也不會一樣呀
→ ledia:也就是你的 A, B, C, D 的 bit 數並不相同
→ ledia:如此失焦下去, 什麼時候才能開始討論演算法呢?
推 ledia:最後... 我想講到這你再不同意 我也掰不出別的了
→ ledia:所以我就此打住 也讓板主方便 ^^:
推 ephesians:我講的是random access memory
→ ephesians:你還可以回答我a[65535]是一個動作還是65535個動作?
→ ephesians:A,B,C,D是隨便舉例的,你還真的討論bit數,我昏了