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

[LPH66 ((short)(-15074))]

程式恕刪

你這個看起來像是影像處理的東西  一次要把一整塊的像素值加起來做處理

先說結論  你要的事情可以用兩次兩層 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)
推 holymars:Sum area
→ netsphere:DP
→ flyingnick:我要把每一個20x20的block加一起..然後一次只間隔一個
→ flyingnick:再取20*20..所以我才會寫O(n^4)..但放在硬體執行後會慢
→ flyingnick:個四,五秒..我試過O(n^3)硬體執行勉強ok...
推 pizza0117:這叫做Integral Image
推 holymars:http://en.wikipedia.org/wiki/Summed_area_table
→ flyingnick:請問要如何壓到O(n^3)呢..