Fragen zu Algorithmen

1 Quicksort

Führen Sie einen Durchlauf des Quicksorts zum Teilen des ersten Intervalls manuell durch. Teilen Sie ein gegebenes Sortierintervall (siehe Aufgabe „Vorher“) nach den Regeln des Quicksorts in zwei Unterintervalle die noch sortiert werden müssen.

  • Sortieren Sie aufsteigend 
  • Wählen Sie das Pivotelement ganz rechts im Intervall. Das Pivotelement soll zum größeren Intervall gehören.
  • Markieren Sie das Pivotelement im „Vorher“ Diagramm mit einem Pfeil von unten (siehe Beispiel).
  • Wenden Sie die Regeln des Quicksorts an. Zeichnen Sie zweiseitige Pfeile im "Vorher" Diagram ein, um die notwendigen Vertauschungen zu markieren.
  • Zeichnen Sie mit einem zweiseitigen Pfeil die nötige Vertauschung des Pivotelements im "Vorher" Diagramm ein.
  • Tragen Sie alle neuen Werte im "Nachher" Diagramm ein.
  • Zeichnen sie die beiden neuen zu sortierenden Intervalle mit eckigen Linien im „Nacher“ Diagramm ein.

Quicksortübung

Die Antwort finden Sie auf der nächsten Seite (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 8 Minuten

2 Quicksort, Pivotelement

Wählt man beim Quicksort das Pivotelement immer am gleichen Rand des Intervals, so gibt es Zahlenreihen die nur sehr ineffizient sortiert werden.
Für welche Zahlenreihen trifft dies zu? Geben Sie ein Beispiel an.

Die Antwort finden Sie auf der nächsten Seite (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 2 Minuten

Antwort zu Frage 1: Quicksort

Quicksortlösung 

3 Ungünstige Zahlenreihen für den Quicksort

Warum funktioniert das „Teile und Herrsche“ Prinzip des Quicksorts bei unvorteilhaften Zahlenreihen nicht gut?

Beispiele sind die folgenden Zahlenreihen

  • 1,2,3,4,5
  • 5,4,3,2,1

Die Antwort finden Sie auf der nächsten Seite (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 2 Minuten

Antwort zu Frage 2: Quicksort, Pilotelement

Aufsteigende oder fallende Zahlenfolgen. z. Bsp. 1,2,3,4,5 oder 5,4,3,2,1

4 Heapsort, Baumpräsentation, Heapbedingung

Zeigen Sie wie der logische Baum eines Heapsorts für ein gegebenes Feld von Schlüsseln aussieht.
Tragen Sie die Schlüssel und den Feldindex (die Feldposition) der Feldrepräsentation in die Heappräsentation unten ein.

Im Beispiel unten ist auf der Position 1 der Schlüssel 9 zu finden.
Tragen Sie Positionen und Schlüssel in das vorgegebene Baumdiagramm ein:

Diagramm eines Heapsorts

Gilt die Heapbedingung für diese Folge? Markieren Sie Knoten die die Heapbedingung verletzen.

Die Antworten finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 5+2 Minuten

Antwort zu Frage 3: Ungünstige Zahlenreihen für den Quicksort

Weil keine ähnlich großen Teilintervalle entstehen.

Im schlimmsten Fall wird das Teilintervall immer nur um ein Element verkleinert.

Der Aufwand ist dann (n-1)+O(n-2)+...+O(3)+O(2)=O(n2) (Arihmetische Reihe)

Der Aufwand zum Bearbeiten der Teilintervalle kann dann im schlimmsten Fall O(n2) anstatt O (log(n)) wie bei ähnlich großen Teilintervallen sein.

5 Erklärung der Heapbedingung

Beschreiben in Worten was die „Heapbedingung“ des Heapsorts ist.

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 3 Minuten

Antwort zu Frage 4: Heapsort, Baumpräsentation, Heapbedingung

Diagramm eines Heapsorts

Die Heapbedingung gilt nicht für diese Folge. Sie ist für die Position 4 (Wert 1) verletzt.

6 Komplexitätsbetrachtungen 1

Welche Komplexität haben die gezeigten Javamethoden?

Gegeben ist das folgende Javaprogramm:

Nr. Quellcode Antwort
 
public class K1 {

private static int groesse = 1000;

public static void main(String[] args) {
algorithmusBsp(groesse);
algorithmus1(groesse);
algorithmus2(groesse);
algorithmus3(groesse);
algorithmus4(groesse);
}

 nichts eintragen
 Bsp.
static void algorithmusBsp(int n) {
  for (int i = 1; i < n; i++) {
    int k = i * 2;
  }
  for (int j = 1; j < n; j++) {
    int k = j * 3;
    }
}
Beispiel:
Ofor1(n)+Ofor2(n) = O(n) 
1. 
static void algorithmus1(int n) {
  for (int i = 1; i < n; i++) {
    int k = i * 2;
  }
  for (int i = 1; i < 1000; i++) {
    int k = i +2;
  }
}
 
 2.
static void algorithmus2(int n) {
  for (int i = 1; i < n; i++) {
    int p = n;
    for (int j = 1; j < p; j++) {
      int k = j - i;
    }
  }
} 
 
 3.
static void algorithmus3(int n) {
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < n; j++) {
      for (int k = 1; k < n; k++) {
        int q = k - j - i;
      }
      int p=0;
        while (p<n) {
          p++;
          int r = n*p;
        }
    }
  }
}          
 
 4.
static void algorithmus4(int n) {
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < 1000; j++) {
      algorithmus2(n);
    }
  }
}
            
 
 
}// Ende der Klasse
 Nichts eintragen

 

Die Antwort finden Sie auf der nächsten Seite (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 8 Minuten

Antwort zu Frage 5: Erklärung der Heapbedingung

Das Feld soll aufsteigend sortiert werden.
Jeder Vaterknoten muss größer als beide Unterknoten sein oder auch: jeder Knoten mit dem Index i muss größer als existierende Knoten mit Index 2*i und 2*i+1 sein.

7 Komplexitätsbetrachtungen 2

Tragen Sie die Aufwände O(n) für die gegeben Methoden des Javaprogramm ein.

Nr. Quellcode Antwort
 
public class K1 {
private static int groesse = 1000;
public static void main(String[] args) {
algorithmusBsp(groesse);
algorithmus1(groesse);
algorithmus2(groesse);
algorithmus3(groesse);
algorithmus4(groesse);
 Nichts in dieses Feld eintragen!
 Bsp.
  static void algorithmusBsp(int n) {
for (int i = 1; i < n; i++)
{ int k = i * 2; }
for (int j = 1; j < n; j++)
{ int k = j * 3;}
}
Beispiel:
Ofor1(n)+Ofor2(n) = O(n)
1.
  static void algorithmus1(int n) {
for (int i = 1; i < n; i++) {
int k = i * 2;
}
int i = 0;
while (i<1000) {
i++;
int k = i +2;
}
}
 
2.
  static void algorithmus2(int n) {
for (int i = 1; i < n; i++) {
int p = n;
for (int j = 1; j < p; j++) {
for (int k = 1; k < n; k++) {
int s = j*k – i;
}
}
}
}
 
3.
  static void algorithmus3(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
int k= 0;
while (k<n) {
k++;
int q = k - j - i;
}
int p=0;
while (p<n) {
p++;
int r = n*p;
}
}
}
}
 
4.
  static void algorithmus4(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < 1000; j++) {
algorithmus2(n);
}
}
}
 
 
 }// Ende der Klasse
 ---

 

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 8 Minuten

Antwort zu Frage 6: Komplexitätsbetrachtungen 1

Gegeben ist das folgende Javaprogramm:

Nr. Quellcode Antwort
 
public class K1 {

private static int groesse = 1000;

public static void main(String[] args) {
algorithmusBsp(groesse);
algorithmus1(groesse);
algorithmus2(groesse);
algorithmus3(groesse);
algorithmus4(groesse);
}

 nichts eintragen
 Bsp.
static void algorithmusBsp(int n) {
  for (int i = 1; i < n; i++) {
    int k = i * 2;
  }
  for (int j = 1; j < n; j++) {
    int k = j * 3;
    }
}
Beispiel:
Ofor1(n)+Ofor2(n) = O(n) 
1. 
static void algorithmus1(int n) {
  for (int i = 1; i < n; i++) {
    int k = i * 2;
  }
  for (int i = 1; i < 1000; i++) {
    int k = i +2;
  }
}
O(n)+O(1000)=O(n) 
 2.
static void algorithmus2(int n) {
  for (int i = 1; i < n; i++) {
    int p = n;
    for (int j = 1; j < p; j++) {
      int k = j - i;
    }
  }
} 
O(n)*O(n)=O(n2)
 3.
static void algorithmus3(int n) {
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < n; j++) {
      for (int k = 1; k < n; k++) {
        int q = k - j - i;
      }
      int p=0;
        while (p<n) {
          p++;
          int r = n*p;
        }
    }
  }
}          
O(n)*O(n)*[O(n)+O(n)]=O(n3)
 4.
static void algorithmus4(int n) {
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < 1000; j++) {
      algorithmus2(n);
    }
  }
}
            

O(n)*[O(1000)*O(algorithmus2)]=

O(n)*O(algorithmus2)=O(n3)

 
}// Ende der Klasse
 Nichts eintragen

8 Komplexitätsbetrachtungen 3

Welchen Aufwand O haben die Methoden algorithmus1() bis algorithmus8() des folgenden Programms abhängig vom Übergabeparameter n?

Gehen Sie davon aus, das der Java JIT (Just in Time Compiler) nichts optimiert.

Hinweis: Wie oft werden die jeweiligen Schleifen durchlaufen? Welche Durchläufe sind konstant, welche variabel?

package Kurs2.Sort;

public class Komplexität {

private static int groesse = 1000;

public static void main(String[] args) {
algorithmus1(groesse);
algorithmus2(groesse);
algorithmus3(groesse);
algorithmus4(groesse);
algorithmus5(groesse);
algorithmus6(groesse);
algorithmus7(groesse);
}

public static void algorithmus1(int n) {
for (int i = 1; i < n; i++) {
int k = i * 2;
}
}

public static void algorithmus2(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < 1000; j++) {
int k = j - i;
}
}
}

public static void algorithmus3(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
int k = j - i;
}
}
}

public static void algorithmus4(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
for (int k = 1; k < n; k++) {
int q = k - j - i;
}
}
}
}

public static void algorithmus5(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < 1000; i++) {
int k = j - i;
}
for (int j = 1; j < 1000; j++) {
int k = j - i;
}
}
}

public static void algorithmus6(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < i; j++) {
int k = j - i;
}
}
}

public static void algorithmus7(int n) {
for (int i = 1; i < 1000; i++) {
int j = 0;
while (j < 1000) {
j++;
int k = 2 * j;
}
}
}

public static void algorithmus8(int n) {
for (int i = 1; i < n; i++) {
algorithmus1(n);
}
}

} // Ende der Klasse

 

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 16 Minuten

Antwort zu Frage 7:Komplexitätsbetrachtungen 2

Nr. Quellcode Antwort
 
public class K1 {
private static int groesse = 1000;
public static void main(String[] args) {
algorithmusBsp(groesse);
algorithmus1(groesse);
algorithmus2(groesse);
algorithmus3(groesse);
algorithmus4(groesse);
 Nichts in dieses Feld eintragen!
 Bsp.
  static void algorithmusBsp(int n) {
for (int i = 1; i < n; i++)
{ int k = i * 2; }
for (int j = 1; j < n; j++)
{ int k = j * 3;}
}
Beispiel:
Ofor1(n)+Ofor2(n) = O(n)
1.
  static void algorithmus1(int n) {
for (int i = 1; i < n; i++) {
int k = i * 2;
}
int i = 0;
while (i<1000) {
i++;
int k = i +2;
}
}
Ofor1(n)+Ofor2(1000)= Ofor1(n)+Ofor2(1) = O(n)
2.
  static void algorithmus2(int n) {
for (int i = 1; i < n; i++) {
int p = n;
for (int j = 1; j < p; j++) {
for (int k = 1; k < n; k++) {
int s = j*k – i;
}
}
}
}
 Ofor1(n)*Ofor2(n)*Ofor3(n) = O(n3)
3.
  static void algorithmus3(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < n; j++) {
int k= 0;
while (k<n) {
k++;
int q = k - j - i;
}
int p=0;
while (p<n) {
p++;
int r = n*p;
}
}
}
}
Ofor1(n)*Ofor2(n)*(Owhile1(n)+Owhile2(n))
Ofor1(n)*Ofor2(n)*2*Owhile(n)= 2*O(n3) = O(n3
4.
  static void algorithmus4(int n) {
for (int i = 1; i < n; i++) {
for (int j = 1; j < 1000; j++) {
algorithmus2(n);
}
}
}
 Ofor(n)*Ofor2(1000)*Oalgorithmus2(n3) = O(n4)
 
 }// Ende der Klasse
 ---

9 Binäre Suche

Fügen im folgenden Beispiel eine binäre Suche nach dem vorgegebenen Schlüssel durch. Zeichnen Sie die notwendigen Vergleiche mit Hilfe von Pfeilen wie im Beispiel der sequentiellen Suche ein:

Sequentielle und binäre Suche

Wieviele Vergleiche benötigen Sie bei der binären Suche in der obigen Folge mit 15 Elementen maximal bis der Schlüssel gefunden ist?

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 3+1 Minuten

Antwort zu Frage 8: Kompexitätsbetrachtungen 3

Quellcode Antworten mit Erklärung
package Kurs2.Sort;
public class Komplexitaet;
  private static int groesse = 1000;

  public static void main(String[] args) {
    algorithmus1(groesse);
    algorithmus2(groesse);
    algorithmus3(groesse);
    algorithmus4(groesse);
    algorithmus5(groesse);
    algorithmus6(groesse);
    algorithmus7(groesse);
  }
 
  public static void algorithmus1(int n) {
    for (int i = 1; i < n; i++) {
      int k = i * 2;
    }
  }
Die for-Schleife wird n mal durchlaufen: O(n) 
  public static void algorithmus2(int n) {
    for (int i = 1; i < n; i++) {
      for (int j = 1; j < 1000; j++) {
       int k = j - i;
      }
    }
  }

Die innere for-Schleife wird 1000 mal durchlaufen:

  • O(1000) = Oinnere(1)

Die äussere for-Schleife wird n mal durchlaufen:

  • O(n)*Oinnere(1)=Oaeussere(n)

Gesamtkomplexität: O(n)

  public static void algorithmus3(int n) {
    for (int i = 1; i < n; i++) {
      for (int j = 1; j < n; j++) {
        int k = j - i;
      }
   }
  }
Die innere for-Schleife wird n mal durchlaufen: 
  • Oinnere(n)

Die äussere for-Schleife wird n mal durchlaufen:

  • O(n)*Oinnere(n)=Oaeussere(n2)

Gesamtkomplexität: O(n2)

  public static void algorithmus4(int n) {
    for (int i = 1; i < n; i++) {
      for (int j = 1; j < n; j++) {
        for (int k = 1; k < n; k++) {
          int q = k - j - i;
        }
      } 
    }
  }

Die innere for-Schleife wird n mal durchlaufen:

  • Oinnere(n)

Die mittlere for-Schleife wird n mal durchlaufen:

  • O(n)*Oinnere(n) = Omittlere(n2)

Die äussere for-Schleife wird n mal durchlaufen:

  • O(n)*Omittlere(n2)= Oaeussere(n3)

Gesamtkomplexität: O(n3)
 

  public static void algorithmus5(int n) {
    for (int i = 1; i < n; i++) {
      for (int j = 1; j < 1000; j++) {
        int k = j - i;
      }
      for (int j = 1; j < 1000; j++) {
        int k = j - i;
      }
    }
  }

Jede der inneren Schleifen wird 1000 mal durchlaufen und hat damit einen konstanten Aufwand

  • Oinnere2(1000)+Oinnere2(1000)= Oinnere2(1)+Oinnere2(1)=Oinnen(1)

Die äussere Schleife wird n mal durchlaufen:

  • O(n)*Oinnen(1)=Oaeussere(n)

Gesamtkomplexität: O(n)

  public static void algorithmus6(int n) {
    for (int i = 1; i < n; i++) {
      for (int j = 1; j < i; j++) {
        int k = j - i;
      }
    }
  }

Jede der inneren Schleifen wird i mal durchlaufen:

  • Oinnen(i)

Die äussere Schleife wird n mal durchlaufen:

  • O(n)*Oinnen(i)

Beide Schleifen haben gemeinsam die Durchläufe 1+2+3... +n = (n-1)n/2 = (n2-n)2

  • O(n)*Oinnen(i)=(O(n2)-O(n))/O(2)=O(n2)/O(1)=Oaussen(n2)

Gesamtkomplexität: O(n2)
Bemerkung: Das Zusammenwirken geschachtelter Schleifen ist nicht trivial. Es müssen alle relevanten Variablen aufgelöst und es muss eine Summenformel entwickelt werden.

   public static void algorithmus7(int n) {
    for (int i = 1; i < 2000; i++) {
      int j = 0;
      while (j < 1000) {
        j++;
        int k = 2 * j;
      }
    }
  }

Die while-Schleife wird 1000 mal durchlaufen. Ihr Aufwand ist konstant:

  • Owhile(1000)=Owhile(1) 

Die for-Schleife wird wird 2000 mal durchlaufen. Ihr Aufwand ist konstant:

  • O(2000)*Owhile(1)=O(1)*Owhile(1)=Ofor(1)

Gesamtkomplexität: O(1)

  public static void algorithmus8(int n) {
    for (int i = 1; i < n; i++) {
      algorithmus1(n);
    }
  }

Die Methode algorithmus1() hat den Aufwand O(n). Siehe weiter oben.

Die for-Schleife wird n mal durchlaufen:

  • O(n)*O(n)=Ofor(n2)

Gesamtkomplexität: O(n2)

} // Ende der Klasse

 

10 Aufwand binäre Suche und sequentielle Suche

  • Welchen Aufwand O() hat die binäre Suche?
  • Welchen Aufwand O() hat die sequentielle Suche?

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 2 Minuten

Antwort zu Frage 9: Binäre Suche

Beispiel einer binären Suche

Man benötigt maximal 4 Vergleiche.

11 Komplexitätsbetrachtungen 4

Tragen Sie die Aufwände O(n) für die gegeben Methoden des Javaprogramm ein.

Nr. Quellcode Antwort
 
public class K1 {
   private static int groesse = 1000;
 
   public static void main(String[] args) {
     algorithmusBsp(groesse);
     algorithmus1(groesse);
     algorithmus2(groesse);
     algorithmus3(groesse);
     algorithmus4(groesse);
   } 
 Nichts in dieses Feld eintragen!
 Bsp.
  static void algorithmusBsp(int n) {
     for (int i = 1; i < n; i++)
        { int k = i * 2; }
     for (int j = 1; j < n; j++)
        { int k = j * 3;}
   }
Beispiel:
Ofor1(n)+Ofor2(n) = O(n)
1.
  static void algorithmus1(int n) {
    for (int i = 1; i < n; i++) {
      int p = n;
      for (int j = 1; j < p; j++) {
        for (int k = 1; k < n; k++) {
          int s = j*k – i;
        } // end for
      } // end for
    } // end for
  }
 
2.
  static void algorithmus2(int n) {
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < n; j++) {
      int k= 0;
      while (k<n) {
         k++;
         int q = k - j - i;
      }
      int p=0;
      while (p<n) {
          p++;
          int r = n*p;
       } // end while
    } // end for
  } // end for
}
 
3.
  static void algorithmus3(int n) {
  for (int i = 1; i < n; i++) {
   for (int j = i; j < n; j++) {
    int k=0;
    while (k<1000000) {  
      k++;
      int r = i*j*k;
 } // end while
   } // end for
  } // end for
}
 
4.
  static void algorithmus4(int n) {
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < 1000; j++) {
      algorithmus1(n);
    }
  }
}
 
 
 }// Ende der Klasse
 ---

 

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 8 Minuten

Antwort zu Frage 10: Aufwand binäre und sequentielle Suche

  • Aufwand O() der binären Suche: O(log(n))
  • Aufwand O() der sequentiellen Suche: O(n)

12 Bubblesort

Der BubbleSort besteht aus einer äusseren Schleife in der das zu sortierende Intervall jeweils verkleinert wird.
In einer inneren Schleife wird das größte Element als « Bubble » bestimmt. Führen Sie einen solchen Durchlauf einer inneren Schleife an der unten gezeigten Folge durch. Sortieren sie aufsteigend.

Markieren Sie alle notwendigen Vergleiche und Vertauschungen.
Fügen Sie alle Werte in das Diagramm ein
 Diagramm einer Folge die im Bubblsort sortiert werden soll

Welchen Aufwand O() hat der Bubblesort?

In welchem Fall ist ein aufsteigend sortierender Bubblesort ein sehr effizienter Algorithmus?

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 8+1+1 Minuten

Antwort zu Frage 11: Komplexitätsbetrachtungen 4

Nr. Quellcode Antwort
 
public class K1 {
   private static int groesse = 1000;
 
   public static void main(String[] args) {
     algorithmusBsp(groesse);
     algorithmus1(groesse);
     algorithmus2(groesse);
     algorithmus3(groesse);
     algorithmus4(groesse);
   } 
 Nichts in dieses Feld eintragen!
 Bsp.
  static void algorithmusBsp(int n) {
     for (int i = 1; i < n; i++)
        { int k = i * 2; }
     for (int j = 1; j < n; j++)
        { int k = j * 3;}
   }
Beispiel:
Ofor1(n)+Ofor2(n) = O(n)
1.
  static void algorithmus1(int n) {
    for (int i = 1; i < n; i++) {
      int p = n;
      for (int j = 1; j < p; j++) {
        for (int k = 1; k < n; k++) {
          int s = j*k – i;
        } // end for
      } // end for
    } // end for
  }
Ofor1(n)*Ofor2(n)*Ofor3(n) = O(n3
2.
  static void algorithmus2(int n) {
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < n; j++) {
      int k= 0;
      while (k<n) {
         k++;
         int q = k - j - i;
      }
      int p=0;
      while (p<n) {
          p++;
          int r = n*p;
       } // end while
    } // end for
  } // end for
}

Ofor1(n)*Ofor2(n)*(Owhile1(n)+Owhile2(n)) =

Ofor1(n)*Ofor2(n)*O(n) =

O(n3

3.
  static void algorithmus3(int n) {
  for (int i = 1; i < n; i++) {
   for (int j = i; j < n; j++) {
    int k=0;
    while (k<1000000) {  
      k++;
      int r = i*j*k;
 } // end while
   } // end for
  } // end for
}

Ofor1(n)*Ofor2(n)*(Owhile1(1000)) =

Ofor1(n)*Ofor2(n) =

O(n2

4.
  static void algorithmus4(int n) {
  for (int i = 1; i < n; i++) {
    for (int j = 1; j < 1000; j++) {
      algorithmus1(n);
    }
  }
}

Ofor1(n)*Ofor2(1000)*Oalgorithmus1(n) =

Ofor1(n)*O(n3) =

O(n4

 
 }// Ende der Klasse
 ---

13 Komplexitätsbetrachtungen 5

Ein Algorithmus A und B verarbeiten jeweils n Datensätzen.

  • Algorithmus A benötigt einmalig 50000000 Instruktionen mehr als Algorithmus B beim Starten. Ansonsten ist die Anzahl der Instruktionen pro Datensatz konstant.
  • Algorithmus B benötigt 4 mal mehr Instruktionen pro Datensatz als Algorithmus A

Leiten Sie die beiden Komplexitätsklassen der Algorithmen her.

Vergleichen Sie die beiden Komplexitätsklassen und geben Sie eine kurze Erklärung.

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 4+4 Minuten

Antwort zu Frage 12: Bubblesort

Bubblesort mit Musterlösung

Welchen Aufand O() hat der Bubblesort ?

O(n2)

In welchem Fall ist ein aufsteigend sortierender Bubblesort ein sehr effizienter Algorithmus?

Bei einer vorsortierten Folge

14 Sortiergrenze beim Insertionsort (Sortieren durch Einfügen)

Was ist die Sortiergrenze in der Folge in der durch Sortieren durch Einfügen
sortiert wird?

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 2 Minuten

Antwort zu Frage 13: Komplexitätsbetrachtungen 5

OA (n) =O (5000000+k*n)=O (1)+O (n)=OA (n)

OB (n) =OA (4n)= OA (n)

Beide Algorithmen sind in der gleichen Komplexitätsklasse. Der zweite Algorithmus wird bei sehr kleinen Anzahlen etwas schneller sein.

15 Sortieren durch Einfügen: Ein Beispiel

Die unten aufgeführte Folge im Diagramm wird aufsteigend sortiert und ist schon teilsortiert. Markieren Sie im Diagramm die Sortiergrenze mit einem Pfeil.

Führen Sie nun einen Durchlauf des Insertionsorts durch.

  • Vergleichen und Tauschen Sie den nächsten Wert solange bis er an der richtigen Stelle steht (3 Min.)
  • Markieren Sie die neue Sortiergrenze mit einem Pfeil (1 Min.)

Hinweis: Markieren Sie eine nötige Vertauschung wie im Beispiel gezeigt.
Tragen Sie dann die neuen Werte in die nächste Zeile ein.
Benutzen Sie dann eine neue Zeile.

Übung Insertionssort

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 1+4 Minuten

Antwort zu Frage 14: Sortiergrenze beim Insertionsort (Sortieren durch Einfügen)

Die Grenze zwischen der unsortierten und der sortierten Folge

16 Fragen zum Sortieren durch Einfügen

Ein paar Fragen zum Sortieren durch Einfügen...

  • Welchen Komplexitätsaufwand hat dieser Algorithmus?
  • Nennen Sie zwei Algorithmen aus der Vorlesung die eine bessere Aufwandsklasse besitzen.
  • Welchen Vorteil hat der Insertionsort immer gegenüber den beiden Algorithmen die eine bessere Komplexitätsklasse besitzen?

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 1+2+2 Minuten

Antwort zu Frage 15 Sortieren durch Einfügen: Ein Beispiel

Lösung zur Aufgabe Soertieren durch EInfügen

Die Antwort zur aktuellen Frage finden Sie viel weiter unten

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Antwort zu Frage 16: Fragen zum Sortieren durch Einfügen

  • Durchschnittlicher Aufwand: Oinsertionsort(n) = O(n2)
  • Effizientere Sortierverfahren
    1. Quicksort
    2. Heapsort
  • Er ist stabil.