Fasst ein Array und Big O Notation

Question

Wie man einen Algorithmus zur Berechnung des Summenwertes in der Matrix finden ??

Sie ist so etwas wie das?

Algorithm Array Sum
Input: nonnegative integer N, and array A[1],A[2],...,A[N]
Output: sum of the N integers in array A
Algorith Body:
j:=1
sum:=0
while j<N
      sum := sum + a[J]
      j:=j+1
  end while
end Algorithm Array Sum

Und wie ich es mit der Laufzeit des Algorithmus beziehen kann mit O-Notation

Dies ist die vergangene Jahr Prüfung und ich brauche Revision für meine Prüfung zu machen.

Frage
Ein Array A [] Halte n ganzzahlige Wert ist gegeben
1.Give ein Algorithmus zur Berechnung der Summe aller den Wert in dem Array
2.Suchen die einfachste und beste O-Notation für die Laufzeit des Algorithmus.

Answer 1

Die Frage ist, die Summe aller Werte zu finden , so durchläuft jedes Element in dem Array und fügen Sie jedes Element in einen temporären Summenwert.

temp_sum = 0
for i in 1 ...array.length
    temp_sum = temp_sum + array[i]

Da Sie müssen alle Elemente im Array zu durchlaufen, das Programm hängt linear mit der Anzahl der Elemente . Wenn Sie 10 Elemente haben, iterieren 10 Elemente durch, wenn Sie eine Million haben Sie keine andere Wahl, als andere zu gehen durch alle Millionen Elemente und fügen Sie jeden von ihnen. So ist die Zeitkomplexität ist Θ (n) .

Wenn Sie die Summe aller Elemente zu finden, und man weiß nicht, irgend etwas über die Daten, dann müssen Sie alle Elemente mindestens einmal zu sehen. Somit ist die n UntereGrenze. Sie müssen auch nicht auf das Element mehr als einmal aussehen. n ist auch die obere Grenze. Daraus ergibt sich die Komplexität Θ (n).

Wenn Sie jedoch etwas über die elements..say wissen Sie sequency von n natürlichen Zahlen zu erhalten, können Sie es in konstanter Zeit mit n tun (n + 1) / 2. Wenn die Daten, die Sie zufällig bekommen, dann haben Sie keine andere Wahl, aber tun, um den obigen linearen Algorithmus.

Answer 2

Da n ist die Größe des Arrays und alles, was Sie tun müssen, ist Iterierte von begeinning die die Big O-Notation zu beenden, ist O [n]

integer N= Size_array;
array a[N]
j=1 
sum=0
while j<=N 
 sum += a[j]  
 j++
end while

Answer 3

Ich denke, dass Sie "während j <= N" bedeutet, müssen Sie dies angeben.

Die Laufzeit soll seine O (n), ich denke, da Sie nur eine Schleife haben.

Answer 4

Um O für diesen Algorithmus berechnen Sie die Anzahl der einzelnen Codezeile führt zählen müssen. Später werden Sie nur die grundlegenden Operationen zählen, sondern beginnen, indem alle zu zählen.

Wie oft wird die j: = 1 Zeile laufen? Wie oft wird die Summe: = 0 laufen? Wie oft wird der Zustand des while-Schleife ausführen? Die Anweisungen innerhalb der while-Schleife?

Sum diese alle auf. Sie werden feststellen, dass der Wert, den Sie so etwas wie 1 + 1 + n + n + n = 2 + 3 n wird erhalten. daher kann man schließen, dass es eine lineare Funktion auf n.