Komplexitäts des Algorithmus in Big Oh, Big Omega und Theta

Question

Ich versuche, die folgende Frage auf rechnerische Komplexität zu lösen:

Berechnen Sie die Berechnungskomplexität des folgenden Algorithmus und aufschreiben seine Komplexität in Big O , Big Omega und Theta

for i=1 to m { 
    x(i) =0; 
    for j=1 to n { 
     x(i) = x(i) + A(i,j) * b(j) 
    } 
} 

wo A ist mxn und b ist nx1.

landete ich mit Big O O(mn^2) Big Omega(1) und Theta(mn^2) auf.

Answer 1

Unter der Annahme, dass die folgende Anweisung in konstanter Zeit läuft:

x(i) = x(i) + A(i,j) * b(j) 

diese somit in O (1) geschehen ist, und hängt nicht von den Werten für i und j. Da Sie in der inneren for Schleife über diese Aussage laufen, genau n mal, kann man sagen, dass der folgende Code ausgeführt wird in O (n):

x(i) =0; 
for j=1 to n { 
    meth1 
} 

(die Zuordnung der Annahme als auch in konstanter Zeit erfolgt). Auch hier kommt es nicht auf den genauen Wert für i an. Schließlich nehmen wir die äußere Schleife in Betracht:

for i=1 to m { 
    meth2 
} 

Verfahren meth2 genau m mal wiederholt wird, so dass eine dichte obere Schranke für die Zeitkomplexität in O (n m).

Da es keine bedingten Anweisungen, noch rekursive und die Struktur der Daten A, b und x nicht die Ausführung des Programms ändern, wird der Algorithmus auch große Omega (mn) und große Theta (Mn).

Natürlich können Sie überschätzen groß oh und unterschätzen großen Omega: für jeden Algorithmus kann man sagen, es ist Ω (1) und für einige, dass es O (2 ⁿ), aber der Punkt ist, dass Sie nicht viel damit kaufen.

Answer 2

Erinnern Sie sich, dass f = Theta(g) wenn und nur wenn f=O(g) und f=Omega(g).

Das Matrix-Vektor-Produkt kann in Theta(mn) Zeit berechnet werden (vorausgesetzt, naive Implementierung) und die Summe der Vektoren in O(m), so dass die Gesamtlaufzeit Theta(mn) ist. Daraus folgt, dass die Uhrzeit auch O(mn) und Omega(mn) ist.