Laufzeit berechnen/Laufzeitanalyse

[java-lehrling]

Hallo zusammen,
ich versuche schon eine ganze Weile Laufzeiten zu berechnen, aber ich verstehe es einfach nicht. Bin regelrecht auf Kriegsfuß damit. Habe mich über Google schon informiert und so Sachen wie "eine for-Schleife wird n-Mal durchlaufen", "wenn es zB nur eine for-Schleife gibt, dann hat das Programm die Laufzeit O(n)", usw, die sind mir klar, allerdings möchte mein Dozent eine Rechnung, wie unten zu sehen. Würde mich echt freuen, wenn mir das jemand erklären kann!
Hier das Beispiel aus der Vorlesung:

public static void insertion_sort(int [] A, int n){

   int i;  /* Indexvariable für innere Schleife*/
   int key;  /* Einzufügender Schlüssel*/
1. for(int j=2; j<=n; j++){
2.   key = A[j];
3. /* Füge A[j] in die sortierte Folge A[1..j-1] ein */
4.   i=j-1;
5.   while ((i>0) && (A[i] > key)){
6.    A[i+1] = A[i];
7.    i--,;
      }
8.  A[i+1] = key;
   }
 }

Mein Problem fängt schon bei der Tabelle, Zeile 2 an. Wieso wird Zeile 2 n-1-mal durchlaufen ?
Und bei den Rechnungen wird zB tj mit (n(n-1)/2 -1) ersetzt. Wieso und woher kommt das ?

Danke schon mal für jegliche Hilfe !

 

[stg]

Mein Problem fängt schon bei der Tabelle, Zeile 2 an. Wieso wird Zeile 2 n-1-mal durchlaufen ?

Die Schleife startet mit j=2 und läuft bis j=n. Nach jedem Durchlauf wird j um 1 erhöht. Also hat man natürlich genau n-1 Durchläufe...

Und bei den Rechnungen wird zB tj mit (n(n-1)/2 -1) ersetzt. Wieso und woher kommt das ?

Da wurde nicht t_j ersetzt, sondern es wurde einfach die Summe berechnet.

 

[JCODA]

Mach dir klar, was for(int j=2; j<=n; j++) bedeutet: du fängst bei 2 an und gehst bis einschließlich n. D.h. n-1 Durchläufe. Deshalb wird Zeile 2 (n-1)-Mal durchlaufen.

Und diese Formel nennt sich "kleiner Gaus" oder "gauß'sche Summenformel": https://de.wikipedia.org/wiki/Gaußsche_Summenformel
Man benutzt sie um Summen der Form
S = 1+2+3+4+5+6+7+...+(n-1) +n
sofort ausrechnen zu können
es ist nämlich S = 1+2+3+4+5+6+7+...+(n-1) +n = n*(n+1)/2

Versuch ruhig diese Formel für einige explizite Werte von n aus und überzeug dich, dass es für diese Werte passt. (Wenn du es "genauer" wissen willst, beweise diese Summenformel durch Induktion...)

Jedenfalls treten solche Summen immer wieder auf, vorallem dann, wenn man zwei verschachtelte Schleifen hat bei denen:
die äußere i von 1 bis n durchzählt
und die innere von 1 bis i

Die "Minus Eins" am Ende der Formel entsteht, da du ja nicht bei 1 sondern bei 2 anfängst, d.h. der "erste" Wert muss noch abgezogen werden.