Informatiker Board | Druckvorschau: Rekursionsgleichung aufstellen

Geschrieben von Shizmo am 09.04.2016 um 22:57:

Rekursionsgleichung aufstellen

Hallo, ich soll von einem rekursiven Sortier-Algorithmus die Rekursionsgleichung aufstellen, um dann mit dem Master-Theorem die Komplexitätklasse abschätzen zu können.

Der Teil mit dem Master-Theorem ist kein Problem, allerdings weiß ich nicht, wie ich eine Rekursionsgleichung zu einem Algorithmus aufstellen soll.

Hier mal der "sehr schlechte" Algorithmus:

code:

1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:

public static void sort(int[] A, int i, int j){
      int help;
      
      if(A[i] > A[j]){
         help = A[i];
         A[i] = A[j];
         A[j] = help;
      }
      
      if(i+1 >= j){
         return;
      }
      
      int k = (j-i+1)/3;
      
      sort(A, i, j-k);
      sort(A, i+k, j);
      sort(A, i, j-k);
   }

Die allgemeine Rekursionsgleichung sieht so aus: $[latex]T(n)=a\cdot T(\frac{n}{b})+f(n)[/latex]$

LG

Geschrieben von eulerscheZahl am 10.04.2016 um 08:51:

Du hast 3 rekursive Aufrufe, also ist a=3.
Die Teilprobleme haben jeweils eine Größe von 2/3 des ursprünglichen Problems (so ungefähr). Also ist b=3/2.
f(n) ist eine Konstante, weil nur ein Vergleich und evtl. eine Vertauschen durchgeführt wird.
Das legt kubische Laufzeit nahe. Hier mal ein Plot mit der Laufzeit (blau - und ja, das ist wirklich so eckig) und x^3/5 (rot).

Geschrieben von Shizmo am 10.04.2016 um 10:49:

Ah okay, super vielen Dank.

Also: $[latex]T(n) = 3T(\frac{2n}{3})+1[/latex]$
Lt. Master-Theorem gilt dann: $[latex]T(n)=\mathcal{O}(n^{log_{1,5}(3)}) \equiv T(n)=\mathcal{O}(n^{2,71})[/latex]$