2016-04-03 15 views
2

im Voraus ist dies eine Hausaufgabe, aber ich habe eine schwierige Zeit Rezidiv-Beziehungen zu verstehen. Ich habe das Internet nach Beispielen durchforstet und sie sind sehr vage für mich. Ich verstehe, dass Rekursionsbeziehungen für rekursive Algorithmen keinen festgelegten Weg haben, um mit jedem umzugehen, aber ich bin darin verloren, diese zu verstehen. Hier ist der Algorithmus Ich muß arbeiten mit:Auswahl Sortierung Rezidiv Relation

void selectionSort(int array[]) { 
    sort(array, 0); 
} 

void sort(int[] array, int i) { 
    if (i < array.length - 1) 
    { 
     int j = smallest(array, i); T(n) 
     int temp = array[i]; 
     array[i] = array[j]; 
     array[j] = temp; 
     sort(array, i + 1); T(n) 
    } 
} 

int smallest(int[] array, int j)  T(n - k) 
{ 
    if (j == array.length - 1) 
     return array.length - 1; 
    int k = smallest(array, j + 1); 
    return array[j] < array[k] ? j : k; 
} 

Also von dem, was ich verstehe, das ist, was ich komme mit: T (n) = T (n - 1) + cn + c Die T (n-1) stellt die rekursive Funktion von sort dar und das addierte cn repräsentiert die rekursive Funktion des kleinsten, die abnehmen sollte, wenn n abnimmt, da es nur die Anzahl von Malen genannt wird, die jedes Mal in dem Array verbleibt. Die Konstante, die mit n multipliziert wird, ist die Zeitmenge, in der der zusätzliche Code am kleinsten ausgeführt wird, und die zusätzliche Konstante ist die Zeitdauer, um den zusätzlichen Code in sort auszuführen. Ist das richtig? Bin ich komplett ausgeschaltet? Erkläre ich es nicht richtig? Auch der nächste Schritt besteht darin, daraus einen Rekursionsbaum zu erzeugen, aber ich sehe diese Gleichung nicht als die Form T (n) = aT (n/b) + c, welche die für den Baum benötigte Form ist, wenn ich dieses Recht verstehe . Ich sehe auch nicht, wie meine Rekursionsbeziehung zu n^2 kommen würde, wenn sie korrekt ist. Das ist auch mein erster Beitrag, also entschuldige ich mich, wenn ich hier etwas falsch gemacht habe. Danke für die Hilfe!

Antwort

1

Der einfachste Weg zur Berechnung der zeitlichen Komplexität besteht darin, die zeitliche Komplexität jeder Funktion mit einer separaten Rekursionsbeziehung zu modellieren.

Wir können die Zeitkomplexität der Funktion smallest mit der Wiederholungsrelation S(n) = S(n-1)+O(1), S(1)=O(1) modellieren. Dies löst offensichtlich S(n)=O(n).

Wir können die Zeitkomplexität der sort Funktion mit T(n) = T(n-1) + S(n) + O(1), T(1)=O(1) modellieren. Der S(n) Begriff kommt, weil wir smallest innerhalb der Funktion sort aufrufen. Weil wir wissen, S(n)=O(n) können wir schreiben T(n) = T(n-1) + O(n), und schreiben die Wiederholung erhalten wir T(n)=O(n)+O(n-1)+...+O(1)=O(n^2).

Also die Gesamtlaufzeit ist O(n^2), wie erwartet.

+0

Also meine Antwort war fast da mit der T (n) = T (n-1) + cn + c? Das ist gut zu wissen, dass ich es irgendwie verstehe. Wäre es korrekter, O (n) oder Θ (n) zu schreiben, da sie in diesem Fall austauschbar wären? oder würden sie? Diesmal ist die Komplexität für mich schwierig. Ich hasse es auch, ein Schädling zu sein, aber wie wird daraus die Wiederholung? Es scheint, als wäre es etwas zwischen (n

+0

Nun, ein Weg, um zu sehen, dass die Summe O (1) + ... + O (n-1) + O (n) zu O (n^2) wird, erinnert daran, dass 1 + 2 + 3 + ... + n = n * (n + 1)/2 = (n^2 + n)/2 = O (n^2). Daraus können Sie folgern, dass sich auch O (1) + ... + O (n) zu O (n^2) addiert. Ja, es ist der Fall, dass T (n) = Theta (n^2) was T (n) = O (n^2) impliziert. Die zeitliche Komplexität ist aus diesen Gründen quadratisch; es ist nicht zwischen n und n^2, zumindest nicht in dem Sinne, dass es für 1 blazs

+0

Vielen Dank für die Erklärung! Also sollte der Rekursionsbaum ... auf jeder Ebene nur einen Zweig haben, oder? Da diese Funktionen an keiner Stelle verzweigen –