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

Re: [問題] ancestry problem

看板Prob_Solve (計算數學 Problem Solving)作者march20時間17年前 (2007/06/23 01:36)推噓0(0推 0噓 0→)

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

※ 引述《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)