Daha iyi çalışma süresine sahip bir algoritma oluşturma

Tüm olası toplamları kaydetmek istediğim A [1], A [2] ..., A [n] ve bir matris B (nxn) numaralı A matrisine sahibim. B matrisi oluşturulur basit bir algoritma şudur:Daha iyi çalışma süresine sahip bir algoritma oluşturma

for i=1,2,...,n 
    for j=i+1,i+2,...,n 
     add the number from A[i] to A[j] 
     save the results to B[i][j] 
    endfor 
endfor

ben (daha iyi çalışma zamanını olması) iyi olması için bu algoritmayı değiştirmek istiyorum. i = 1,2, ... n ila i = 1 için birinciyi değiştirdim ve i ikincisinin sonunda bunu arttırıyorum. Ayrıca ihtiyaç duyduğum daha fazla hesaplama yaptığımı düşünüyorum. B hesaplamak için [1] [5] A [1] [2] + A [1] [3] + A [1] [4] hesaplamalıyım ama bu toplam B de [1] [4] 'dir. Bu yüzden bunu daha az hesaplama ile hesaplayabilirim (B [1] [4] + A [1] [5]). Bu algoritmayı geliştirmeme yardımcı olan var mı?

kaynak

2016-03-23 Lee Yaan

Bu bir vektör veya matris mi? B [i] [j] 'nin tanımının ne olduğunu basit İngilizce ya da bir denklemle yazabilir misiniz? – biziclop

İkinci çözümün verimli ve basit olması, çıktıda gereken her değer için az sayıda aritmetik işlemdir. Çıkışın boyutu olan O (n^2) 'de çalışır, asimptotik karmaşıklık açısından bundan daha iyi olmayacaksınız. – amit

B [1] [5] A [1] [2] + A [1] [3] + A [1] [4] 'i içermemektedir. A [1] [4] + A [1] [5] içerir. Bunu bir yorumda göstermek zor. Burada çıktı ile ilk satır için küçük bir R betiği vardır: [code] local ({A = 1: 5; B = rep (NA, 4); for (j: 2: 5) {B [j] = A [ j-1] + A [j]}; rbind (A = A, B = B)}) [/ code] [kod] A 1 2 3 4 5 [/ code] [kod] B NA 3 5 7 9 [/kod] – DAV

for i=1,2,...,n 
    for j=i,i+1,i+2,...,n 
     if i == j then B[i][j] = A[j] 
     else B[i][j] = B[i][j - 1] + A[j] 
    endfor 
endfor

kaynak

2016-03-23 12:03:49 Sorin

Daha iyi çalışma süresine sahip bir algoritma oluşturma

cevap

İlgili konular