9 Binäre Suche

Submitted by javafrage on Mon, 03/17/2014 - 08:19

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

 

Anonymous (not verified)

Thu, 05/04/2017 - 06:20

Wie kann ich den an der Aufgabenstellung erkennen das es sich um eine sortierte Folge handelt?

Grüße

Für alle i von Null bis zum höchsten Element der Folge f gilt: fi < fi+1