Programmlaufzeit

[DerAhnungsloseDude]

int [] array=randomArray(n);
int a=6;
int b=0;
int cd=array.length-1;
while (b<=cd){
    int m=b+(cd-b)/2;
    if(a<array[m]){
        cd=m-1;
    }else if(a>array[m]){
        b=m+1;
    }else{
        System.out.println(m);
    }
}

Ich soll die beste mögliche Laufzeit(also den best case) dieses Programmfetzens bestimmen . randomArray(n) ist eine Methode die ein Array der Länge l erstellt l soll dabei größer gleich 1 sein aber kleiner gleich n (n ist eine positive Eingabe).
Nun ist meine Frage wie ich hierbei vorgehen muss bei der Laufzeitbestimmung.
Für Tipps und Ansätze wäre ich sehr dankbar.

 

[kneitzel]

Also dazu solltest Du erst einmal den Code anschauen um zu verstehen, was da genau passiert.
Was steckt in den einzelnen Variablen? Evtl. hilft es, dazu die Variablen umzubenennen.

Falls man das nicht sofort versteht, dann spielt man den Code ein paar Mal auf einem Zettel durch.

-> Was ist die Abbruchbedingung?
-> Wie werden die Variablen angepasst?

Dann kann man schon überlegen, was bei einem Array der Größe N an Durchläufen mindestens stattfindet. Und man erkennt dann ggf. auch die maximale Anzahl der Durchläufe....

 

[httpdigest]

Kleiner Hinweis: Dieser Code hat ein Problem, welches die genaue Bestimmung der best-case Laufzeit schwierig gestaltet: Sobald der unkonditionale else-Zweig der if-Anweisung erreicht wird, terminiert der Algorithmus nicht mehr. Ich hoffe/denke aber mal, dass man diesen Fehler in der Aufgabenstellung ignorieren muss/soll - und somit der Algorithmus als terminiert angesehen werden soll.