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:
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:
Die äussere for-Schleife wird n mal durchlaufen:
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:
Die äussere for-Schleife wird n mal durchlaufen:
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:
Die mittlere for-Schleife wird n mal durchlaufen:
Die äussere for-Schleife wird n mal durchlaufen:
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
Die äussere Schleife wird n mal durchlaufen:
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:
Die äussere Schleife wird n mal durchlaufen:
Beide Schleifen haben gemeinsam die Durchläufe 1+2+3... +n = (n-1)n/2 = (n2-n)2
Gesamtkomplexität: O(n2) |
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:
Die for-Schleife wird wird 2000 mal durchlaufen. Ihr Aufwand ist konstant:
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:
Gesamtkomplexität: O(n2) |
} // Ende der Klasse |
|
- Printer-friendly version
- Log in to post comments
- 4589 views
Sortierte Folge
Wie kann ich den an der Aufgabenstellung erkennen das es sich um eine sortierte Folge handelt?
Grüße
Antwort
Für alle i von Null bis zum höchsten Element der Folge f gilt: fi < fi+1