wie die Zeitkomplexität finden Schrittzahl mit

Question

sum(array,n) 
{ 
    tsum=0; 
    for(i=0;i<n;i++) 
    tsum=tsum+array[i]; 
    return tsum; 
} 

Answer 1

In Bezug auf big-O, das ist linear proportional zur Anzahl der Array-Elemente verarbeitet, so O (n)

(Beachten Sie, Ihr Code überschreibt die i-Parameter , angenommen, dass der Parameter n sein sollte, um die Anzahl der zu summierenden Array-Elemente anzugeben?)

Answer 2

Sie deklarieren tsum = 0 in 1 Schritt, dann führen Sie die Schleife für n Schritte aus. In jeder Iteration machen Sie eine Summe, die 1 Schritt ist, und dann geben Sie tsum in 1 Schritt zurück. Ihre Schrittzahl ist ungefähr:

1 + 3n + 1, das ist O (n) in Bezug auf die Groß-Oh-Notation, die Konstanten ignoriert, und alle Terme niedrigerer Ordnung (wenn es eine konstante Anzahl von ihnen gibt.) Es gibt 3n Schritte wie in jeder Iteration, erhöhen Sie die Variable i, überprüfen Sie, ob es kleiner als n ist, und geben Sie dann die Schleife ein, um die Berechnung durchzuführen.

Answer 3

       Cost   Times 
tsum=0;       c1    1 
for(i=0;i<n;i++)    c2    n+1 
    tsum=tsum+array[i];   c3    n 
return tsum;     c4    1 

Die Gesamtkosten des Algorithmus ist 1 * c 1 + (n + 1) c2 + c3 + n 1 * c4

Somit ist die Zeit für diesen Algorithmus erforderlich ist, ist proportional zu n.