Re: [問題] 請問要如何將迴圈簡化..

看板C_and_CPP (C/C++)作者LPH66 ((short)(-15074))時間16年前 (2009/10/05 17:40)推噓2(2推 0噓 0→)

留言2則, 2人參與討論串4/4 (看更多)

※ 引述《LPH66 ((short)(-15074))》之銘言： : 突然想到如果你要的事情是要對 block 操作而不只是要求 sum 的話 : 那就不能做到 O(n^2) 了 : 這樣我倒不如建議你還是用 O(n^4) 的寫法 : (因為你無論如何總得要把那一塊東西抓出來.... : 有一個技巧雖然可以壓到 O(n^3) 左右但程式不好寫... : 如果真是這樣我再回文說好了) : → flyingnick:請問要如何壓到O(n^3)呢.. 10/05 13:45 我大概說個概念...因為詳細寫出來的話頗複雜這個要壓到 O(n^3) 有一個前提就是你的操作不能更動到抓出來的陣列 (如果要更動的話那由於每一次都要抓新的出來 O(n^4) 是跑不掉的) (題外話, 說是 O(n^4) 其實應該是 O(n^2m^2) 啦 (在你這裡 m=20 就是) 所以這裡的 O(n^3) 其實也應該是 O(nm(n+m)) 那這裡你就要了解說你的操作到底值不值得讓抓出陣列的時間壓下來因為如果你的操作仍然是(軟體時間的) O(m^2) 的話那這個陣列抓出來的時間省下來就變得沒有必要了 (因為整體還是 O(n^2m^2)) 還有就是因為這個方法會讓陣列結構變得不直覺如果硬體或是演算法吃不下來的話你還是寫 O(n^2m^2) 的迴圈比較穩...) 做法是這樣的將你的 20x20 陣列看成左右循環也就是 [0][0] => [0][1] => ... => [0][19] => 回到 [0][0] [1][0] => [1][1] => ... => [1][19] => 回到 [1][0] 等等每次往右推進時只換掉一直排剩下的 19 直排不動因此每次的時間是 O(m) 然後用一個變數紀錄現在的左邊是第幾直排到時候存取時就用 [(開始+x)%20][y] 來抓每次要往下推進時由於是處在第一個 n 之內你可以直接把整個 m*m (20x20) 搬過來這樣一來在最外層的 n 之內有一個 O(m^2) 和 n 個 O(m) 的搬移操作全部的時間就是 O(nm(n+m)) 了 --- 其實本來有想說一次抓 km*m 的陣列過來這樣雖然仍舊是 O(n^2m^2) 但會少一個常數倍但仔細想想如果這樣可行的話那就乾脆在原陣列上指來指去就好了.... 所以我這裡還是假設你需要把這 m*m 的值另外抓出來或是放在一起才能做事 (例如說會改到原陣列或是硬體限制要放在一起的) 如果沒關係的話那不妨就用一個指標指過去來算... -- [LPH] Oops, your OOP's a problem? 說: 你現在還是看不到狗? ************* 說: 看得到只是他們不會跑就一直呆呆在那邊一直在起點 [LPH] Oops, your OOP's a problem? 說: 你要按"ㄅㄧㄤˋ"它們才會跑啊@@" -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.28.92