我遇到了問題,並提供了一個OK-ish解決方案。我希望有更好的解決方案。尋找任意子陣列中所有項目總和的最佳算法
問題
我有大約20萬整數數組。給定兩個指數i1和i2,我需要計算i1和i2之間所有元素的總和。數組中的每個整數都在1到4之間。例如:
a = [1, 3, 2, 4, 3, 2, 4, 1];
subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2)
此操作將執行大約200,000次,因此需要非常快。 for循環中的簡單計數器是O(n),而且太慢了。陣列在施工後從不修改,所以可以有相對昂貴的預處理階段。
我最好的解決方案至今
這種算法工作在O(log n)的時間:
第一焊盤原始數組用零,直到其長度爲二的冪。接下來,將數組分成兩個相等的部分並存儲每個的總和。然後將數組分成四個部分並存儲每個部分的總和。然後八分之一。繼續這樣做直到數組被分成2個元素長的段。對於上面的8個元素的陣列,這需要兩個步驟:
halves = [(a[0] + a[1] + a[2] + a[3]), (a[4] + a[5] + a[6] + a[7])]
quarters = [(a[0] + a[1]), (a[2] + a[3]), (a[4] + a[5]), (a[6] + a[7])]
然後給出兩個指數,現在有可能制定出subsection_sum在O(log n)的時間。例如,subsection_sum(a,2,7)== quarters [1] + halfves [1]。
完美,我不敢相信我想到了這樣一個複雜的解決方案,錯過了一個簡單的解決方案!謝謝。 – 2011-05-22 14:36:39
與我的解決方案一樣,但是卻擊敗了我! +1 – 2011-05-22 14:38:08