Re: [問題] ancestry problem
看板Prob_Solve (計算數學 Problem Solving)作者ephesians (ephesians)時間17年前 (2007/06/22 17:30)推噓2(2推 0噓 13→)留言15則, 2人參與討論串12/15 (看更多)
※ 引述《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
→
06/22 17:32, , 1F
06/22 17:32, 1F
→
06/22 17:32, , 2F
06/22 17:32, 2F
→
06/22 17:32, , 3F
06/22 17:32, 3F
→
06/22 17:33, , 4F
06/22 17:33, 4F
→
06/22 17:33, , 5F
06/22 17:33, 5F
→
06/22 17:34, , 6F
06/22 17:34, 6F
→
06/22 17:34, , 7F
06/22 17:34, 7F
→
06/22 17:35, , 8F
06/22 17:35, 8F
→
06/22 17:35, , 9F
06/22 17:35, 9F
→
06/22 17:35, , 10F
06/22 17:35, 10F
推
06/22 17:39, , 11F
06/22 17:39, 11F
→
06/22 17:39, , 12F
06/22 17:39, 12F
推
06/22 17:57, , 13F
06/22 17:57, 13F
→
06/22 17:57, , 14F
06/22 17:57, 14F
→
06/22 17:59, , 15F
06/22 17:59, 15F
討論串 (同標題文章)
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
