Fragen zum Ergebnis bei einem Summenzeichen



  • Hallo,
    in meinen Buch:"Algortihmen eine Einführung" geht es gerade darum die Komplexität eines Insertion-Sort Algorithmuses zu Bestimmen
    Der Pseudocode sieht so aus:

    //   Kosten       Anzahl
    for j = 2 to A.länge                //     c1           n  
    schlüssel = A[j]                    //     c2           n - 1
    
    //Setzte A[j] in das sortierte Teilfeld A[i...j-1] ein.
    i = j - 1                           //     c4           n - 1
                                                              n
    while i > 0 und A[i] > schlüssel {  //     c5         [e]sum[/e] tj
                                                            j = 2   
      A[  A[i+1] = A[i]                 //     c6    // selbe wie oben nur tj -1 
      i = i - 1                         //     c7    // selbe wie oben nur tj -1 
    }
    A[i+1] = schlüssel
    

    Die Frage die ich mir stell ist nun, was genau ist tj und j? Am besten mit einem Beispiel erklärt.
    Im Buch steht dazu noch:"Für jedes j = 2,3---,n mit n = A.länge geben wir mit tj an, wie viele Male die Abfolge der While-Schleife in Zeile 5 für den Wert j ausgeführt wird".

    n
    ∑ tj
    j = 2

    Nomalerweise würde ich davon ausgehen, das die Komplexität = c5 * (wiederholungen der while schleife * die Komplexität des Aufrufes) ist.
    Aber weiso brauche ich dann das Summenzeichen?

    ps. j und die ganzen Zahlen sind immer etwas nach unten versetzt.


Log in to reply