Re: [問題] 請問要如何將迴圈簡化..
看板C_and_CPP (C/C++)作者LPH66 ((short)(-15074))時間16年前 (2009/10/03 07:46)推噓3(3推 0噓 5→)留言8則, 4人參與討論串3/4 (看更多)
程式恕刪
你這個看起來像是影像處理的東西 一次要把一整塊的像素值加起來做處理
先說結論 你要的事情可以用兩次兩層 for 完成
不過做法不太好說明.....
要簡單說的話就是:
任何一塊區域可以這樣求 (使用O(1)的時間)
xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx
xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx
xxxxxxxxx = xxxxxxxxx - xxxxxxxxx - xxxxxxxxx + xxxxxxxxx
xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx
xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx xxxxxxxxx
右邊每一個都是代表從左上角到某處的方形區域的和
這樣所有值就是 O(n^2)
而左上角開始的方形區域和可以再用一個 O(n^2) 另外開一個陣列預處理
(預處理的方法至少有兩種 都是每個位置使用O(1)計算
這就留給你自己好好想想了 提示: 前面預處理完的答案還會有用)
程式的話只要理解了做法很好寫的 也留給你自己去寫了～
--
是說從我知道這個方法以來好像沒聽過這做法有個什麼名字
(當初也是聽別人說才知道的 他也沒有提過名字)
不知道有沒有個好叫的名字...(不然每次都要這樣說有點冗...雖然可以賺P幣 XD)
--
突然想到 如果你要的事情是要對 block 操作 而不只是要求 sum 的話
那就不能做到 O(n^2) 了
這樣我倒不如建議你還是用 O(n^4) 的寫法
(因為你無論如何總得要把那一塊東西抓出來....
有一個技巧雖然可以壓到 O(n^3) 左右 但程式不好寫...
如果真是這樣我再回文說好了)
--
**** 說:
不要期望一個精神力差不多已經見底的人阿Orz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.28.92
※ 編輯: LPH66 來自: 140.112.28.92 (10/03 07:50)
※ 編輯: LPH66 來自: 140.112.28.92 (10/03 07:51)
推
10/03 10:32, , 1F
10/03 10:32, 1F
→
10/03 11:11, , 2F
10/03 11:11, 2F
→
10/03 13:23, , 3F
10/03 13:23, 3F
→
10/03 13:25, , 4F
10/03 13:25, 4F
→
10/03 13:26, , 5F
10/03 13:26, 5F
推
10/03 15:54, , 6F
10/03 15:54, 6F
推
10/03 23:12, , 7F
10/03 23:12, 7F
→
10/05 13:45, , 8F
10/05 13:45, 8F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 3 之 4 篇)：
C_and_CPP 近期熱門文章
PTT數位生活區 即時熱門文章
