Contents Next

1   Einleitung

Literatur: Baut auf Kapitel 1 von [CLR90] auf.
Inhalt Algorithmus ·Analyse von Algorithmen ·Zeitkomplexität und Speicherkomplexität ·Algorithmenentwurf
Aufbau
Algorithmus
Berechnungsproblem: Sortieren


Beispiel: Insertion-Sort


Insertion_sort(A)

  for j = 2 to length[A]
    do key := A[j];
         i :=  j-1;
       while   i > 0 and A[i] > key
          do
               A[i+1] := A[i]
                    i := i-1;

       A[i+1] := key;

  
   





Analyse von Algorithmen


Analyse des Sortierens durch Einfügen




Insertion_sort(A)

 for j = 2 to length[A]            // c1    n
   do key := A[j];                 // c2    n-1
        i :=  j-1;                 // c4    n-1    
      while  i > 0 and A[i] > key  // c5    sum(j=2 to n) t_j
         do
              A[i+1] := A[i]       // c6    sum(j=2 to n) (t_j-1)
                   i := i-1;       // c7          -"-
         od
       A[i+1] := key;              // c8    n-1

Analyse (2)




Insertion_sort(A)

 for j = 2 to length[A]            // c1    n
   do key := A[j];                 // c2    n-1
        i :=  j-1;                 // c4    n-1    
      while  i > 0 and A[i] > key  // c5    sum(j=2 to n) t_j
         do
              A[i+1] := A[i]       // c6    sum(j=2 to n) (t_j-1)
                   i := i-1;       // c7          -"-
         od
       A[i+1] := key;              // c8    n-1



T(n) = c1 n + (c2+c4+c8)(n-1)
   
c5
n
å
j=2
tj + (c6+c7)
n
å
j=2
(tj-1)

Analyse (3)


    tj T(n)
bester Fall sortiert 1 a n + b
schlechtester Fall rückwärts sortiert j a n2 + b n + c
Algorithmenentwurf


D&C: Mergesort


Mergesort (code)




Merge_Sort(A,p,r)
  
  if p < r
     then   q := floor(p+r/2);   // the ``middle''
        Merge_Sort(A,p,q);
        Merge_Sort(A,q+1,r);
        Merge(A,p,q,r);



Analyse von Merge-Sort
January 23, 2001
Contents Next