Hol' Dir diese Lernkarten, lerne & bestehe Prüfungen. Kostenlos! Auch auf iPhone/Android!

Das Ergebnis eines Algorithmus heißt determieniert, wenn es bei vorgegebenen Eingaben immer dasselbe Ergebnis liefert. Voraussetzung ist natürlich, dass die Eingangsparameter gleich sind.


Der Ablauf eines Algorithmus heißt deterministisch, wenn er eine eindeutige Vorgabe für die Folge der auszuführenden Schritte macht.



Ein Algorithmus heißt terminierend, wenn er nach endlich vielen Schritten, abbrechen würde.

=> z.B. eine Endlosschleife ist nicht terminierend, weil die nie abbricht

private void print_order(TreeNode root){
      if (root == null){
          return;
      }
      print_postOrder(root.left);
      print_postOrder(root.right);
      print(root);

      print(root);
      print_preOrder(root.left);
      print_preOrder(root.right);

      print_inOrder(root.left);
      print(root);
      print_inOrder(root.right);
}

static boolean binaer(int [] array, int unter, int oben, int key){
         if (unten > oben){
            return false;
         } else {
                  int mitte = (unten + oben)/2;
                  if(array[mitte]==key){
                      return true;
                   } else if(array[mitte] < key){
                       return binaer(array, mitte +1, oben, key)
                   } else{
                        return binaer (array, unter, mitte - 1, key)
                   }
}
                      
                     

public static void selectionSort(int [] array){
          for (int i = 0; i < array.length - 1; i){
                int min = i;
                for(int j = i + 1; j < array.length; j){
                     if (array[min] > array [j]){
                         min = j;
                     }
                 if (min != i){
                     swap (array, min, i);
                 }
          }
}

- n*n
- instabil**

public void bubbleSort(int [] a){
        for (int i = 0; i < a.length - 1; i){
              for (int j = 0; j < a.length - 1; j){
                    if (a[j] > a[j + 1]){
                        swap (a, j, j +1);
                    }
               }
         }
}


boolean swapped;
do {
     swapped = false;
     for (int i = 0; i < a.length-1; i++){
           if (a [j] > a[j +1]){
               swapped = true;
           }
} while(swapped);

public static void insertionSort(int [] array){
          for (int i = 1; i < array.length; i++){
                int j = i;
                int m = array [i];
                while (j > 0 && array[j - 1] > m){
                          array [j] = array[i - 1];
                          j --;
                }
                array[j] = m;
           }
}



- stabil
- n, bei kleineren Folgen sehr gut, bei fast sortiertem Array gut,

private void quicksort (int [] a, int links, int rechts)
    {
        int i=links;
        int j=rechts;
        int mitte =a[(links+rechts)/2];
        while (i<=j) {   
            while (a[i]< mitte) i;
            while (a[j]>mitte) j;
            if (i<=j) {
                swap(a, i, j);
                i ;
                j ;
            }
        }
        if (links<j) quicksort(a, links, j);
        if (i<rechts) quicksort(a, i, rechts);
    }

  

- abstrahieren von Implementierung
- arbeiten nur mit einer Schnittstelle
- verborgene Implementierung
-

- Jeder Knoten außer dem letzten hat hat genau einen Nachfolger.
- Merkt man sich in einem Knoten immer nur den Nachfolger, dann handelt es sich um eine Lineare Liste (linked list).
- B-Baum: Alle Blätter liegen in derselben Schicht; alle Knoten eiens Baumes der Ordnung n (mit Ausnahme der Wurzel) besitzen zwischen m/2 und m Kinder.

- AVL-Baum: Binärer Such-Baum, bei dem sich für jeden Knoten die Höhe seiner Teilbäume höchstens um 1 differiert.
              - im schlechtesten Fall = O (log n)

public class Liste{
   private ListElement erstes;
  
   public boolean isEmpty(){
       return erstes == null;
   }

  public int getFirst(){
       if (isEmpty()){
          throw new Exception;
       } else {
          return erstes.wert;
       }
}
  
  

public int anzahlVorkommen(int gesucht){
       int zaehler = 0;
       Element e = erstes;
       while (e != null){
           if (e.wert == gesucht){
              zaehler ++;
           }
          e = e.naechst;
      }
      return zaehler;
}


public void addLast(int zahl){
      ListElem neu = new ListElem();
      neu.wert = zahl;
      neu.naechst = null;
      if (erstes == null){
         erstes = neu;
      } else {
         Element e = erstes;
         while (e.naechst != null){
                 e = e.naechst;
          }
          e.naechst = neu;
}    


--

public void removeLast(){
      if (erstes == null){
         throw new Exception;
      } else if (erstes.naechst.naechst == null){
         erstes =null;
      } else {
          ListElem e = erstes;
          while (e.naechst != null){
                 e = e.naechst;
          }
          e.naechst = null;
}


public void removeFirst(){
      if (erstes == null){
          Exception;
      }else if (erstes.naechst == null){
          erstes = null;
      } else {
           erstes = erstes.naechst;
      }
}--

public class Queue{
      private Liste queue;
  
      public Queue(){
           queue = new Liste();
      }

     public int front(){
        return queue.getLast();
     }
    
     public void enter(int zahl){
        queue.addFirst(zahl);
    }

     public void leave(){
        queue.removeLast();
     }

    public boolean isEmpty(){
        if (queue.isEmpty()){
           return true;
       }else false;

1. Mit einer Stoppuhr bestimmen

2. Pseudocode schreiben und Operationen zählen

3. Wie 2., nun werden aber nur die teuren Schritte gezählt (teuer: Vertauschung odr Vergleich)

Dient zur Abschätzung der Aufwandsfunktion

Folgende Vereinfachungen sind möglich:

g = n3 + n2 g = n3
nur größten Exponent berücksichtigen

g = ldn g = log n
nur Logarithmus zur Basis 10 betrachten

g = an g = n
konstante Faktoren weglassen g

g = n + b g = n
konstante Summanden weglassen

Man wählt das linkeste Element und dieses wird mit seinem rechten Nachbarn verglichen. Falls die Reihenfolge nicht stimmt, vertauscht man die beiden Elemente miteinander. Fallt die Reihenfolge stimmt, geht man zum nächsten Element, mit dem zuletzt verglichen wurde. Dieses Element wird mit seinem rechten Nachbarn verglichen.

So geht man bis zum vorletzten Elemen in dem Array vor. Und dann bekommen wir die sortierte Folge.

Man nimmt ein Element aus dem Originalstapel und fügt es in dem Zielstapel hinzu. Unser Zielstapel hat jetzt die Länge 1. Dann nimmt man ein weiteres Element aus dem Originalstapel und fügt es an der richtigen Stelle in den Zielstapel ein.
Muss ein Element an einer Stelle im Zielstapel „dazwischen“ geschoben werden, dann schiebe die rechts davon liegenden Elemente jeweils um eine Position nach rechts.
Falls der Originalstapel nicht leer ist, mach weiter so. Ansonsten haben wir den ursprünglichen Stapel sortiert.

Es gibt 2 Arrays oder Zahlenfolgen: die unsortierte Folge und eine weitere, in der dann die sortierten Zahlen gespeichert werden sollen, die am Anfang leer ist.
Man sucht sich dann das kleinste Element in der unsortierten Folge und danach wird dieses Element am Anfang in die sortierte Folge angefügt. Man macht das solange, bis es keine Elemente mehr in der unsortierten Folge gibt.

Am Beginn hat man ein unsortiertes Array, gegeben über zwei Indices: Beginn und Ende. Falls das Array die Länge 1 (beginn ==ende) hat, ist es bereits sortiert. Ansonsten muss man ein Pivot-Element auswählen. Man kann dieses frei auswählen(ganz links, ganz rechts, mitte). Nachdem man z.B. das rechteste Element als Pivot-Element ausgewählt hat, muss man das ganze Array in Teilen zerteilen, so dass die Elemente in dem Teilarray von Beginn bis Mitte(Pivot) -1 kleiner als das Pivot-Element sind und die Elemente von Mitte + 1 bis Ende größer oder gleich als dem Pivot-Element sind

Das gleiche Verfahren wird dann auf die beiden Teilarray angewendet.