Bir keyfi alt dizideki tüm öğelerin toplamını bulmak için en iyi algoritma nedir

Question

Bir sorunum ve bir Tamam ish çözümüm. Umarım orada daha iyi bir çözüm vardır.

sorun

etrafında 200,000 tamsayılar ile bir dizi vardır. I1 ve i2 olmak üzere iki indeks verildiğinde, i1 ve i2 arasındaki tüm elementlerin toplamını hesaplamam gerekir. Dizideki her tam sayı 1 ile 4 arasındadır. Örneğin,

a = [1, 3, 2, 4, 3, 2, 4, 1]; 
subsection_sum(a, 0, 3); // returns 6: (1 + 3 + 2) 

Bu işlem yaklaşık 200.000 kez gerçekleştirilecektir, bu nedenle oldukça hızlı olması gerekir. For döngüsündeki basit bir sayaç O (n) ve çok yavaştır. Dizi, inşaattan sonra asla değiştirilmez, bu nedenle nispeten pahalı bir ön işleme aşamasına sahip olmak sorun değil.

İlk ped uzunluğu kadar sıfırlarla orijinal dizi ikisinin bir güçtür: My iyi çözüm

bugüne kadar

Bu algoritma O (n günlük) zamanı çalışır. Ardından, diziyi iki eşit parçaya bölün ve her birinin toplamını saklayın. Ardından diziyi dört bölüme ayırın ve her birinin toplamını saklayın. Sonra sekizinci. Dizi, bölüm 2 öğeye bölünene kadar bunu yapmaya devam edin. Yukarıda 8 elemanlı bir dizinin, bu iki aşamada: Daha sonra, iki yanarlar

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])] 

, zaman (log n) O'da subsection_sum çalışmak mümkündür. Örneğin, subsection_sum (a, 2, 7) == quarter [1] + yarımları [1].

Answer 1

Kümülatif toplamı içeren bir yardımcı dizi tanıtın. Yani, yardımcı dizinin i elementi, orijinal dizinin 0 ile i arasındaki elemanlarının toplamına sahiptir. Alt dizi toplamı, yalnızca yardımcı diziden iki elemanın farkıdır. Bu sabit zaman içinde O(1) sonucunu verecektir.

Bu soruya verilen subsection_sum işlevinde bir değişmez bağlıdır ,:

subsection_sum(a, 0, i2) = subsection_sum(a, 0, i1) + subsection_sum(a, i1, i2) 

Ben i1 <= i2 varsayıyorum. Yeniden düzenleme elimizde: Sağ taraftaki toplamlar hem 0 başlamak olduğunu

subsection_sum(a, i1, i2) = subsection_sum(a, 0, i2) - subsection_sum(a, 0, i1) 

Not. Yardımcı dizi, tüm i için sıfırdan subsection_sum(a, 0, i) toplamları için değerlerin önbelleğe alınması olarak görülebilir.

Answer 2

Eğer O(n) ek depolama gelemez, kimin i inci elemanı, giriş dizideki i (dahil) ile endeks 0 de elemanlarının toplamı olan bir arama tablosu oluşturabilir. pseudocode:

def computeLookupTable(arr): 
    let n = arr.length 
    let lookupTable = new Array() 

    lookupTable[0] = arr[0] 

    for i=1 to n: 
     lookupTable[i] = arr[i] + lookupTable[i-1] 

    return lookupTable 

Sonra sabit zaman alır farkı

lookupTable[i2] - lookupTable[i1] 

alarak i1 ve i2 arasındaki array tüm öğelerin toplamını hesaplamak için bu tabloyu kullanabilirsiniz.