Begründen Sie die Korrektheit des Algorithmus und beweisen Sie, dass die gewünschte obere Schranke von …

Question

Aufgabe:

Sei \( A \) eine Liste der Länge \( n \) von paarweise verschiedenen Elementen, auf penen eine totale Ordnung („Vergleichsoperation") definiert ist.

(a) Geben Sie einen Algorithmus (in python- oder Pseudocode) an, der (im schlechtesten Fall) mit \( 3\left\lfloor\frac{n}{2}\right\rfloor \) Vergleichen sowohl das Minimum als auch das Maximum von \( A \) bestimmt.
(b) Begründen Sie die Korrektheit des Algorithmus und beweisen Sie, dass die gewünschte obere Schranke von \( 3\left\lfloor\frac{n}{2}\right\rfloor \) Vergleichen gewährleistet ist. Dabei werden nur Vergleiche der Daten (und keine Indexvergleiche) gezählt.

Problem/Ansatz:

Ich weiß nicht ob mir jemand bei dieser Aufgabe helfen kann, weil diese im Python eigentlich geschrieben werden sollte. Aber falls jemand Ahnung hat wie diese aufzuschreiben ist, wáre ich sehr dankbar fúr einen Tipp.

Answer 1

Aloha :)

Ich kann leider die exakte Python-Syntax nicht, weil wir nicht in Python programmieren. Ich habe dir den Algorithmus daher in Pseudo-Code aufgeschrieben. Du müsstest das dann noch in die Python-Syntax übertragen:

assert( n>=0 && A!=NULL );

i=0; k=n; min=A[0]; max= A[n];

while (i<k) {

    if (A[i]<=A[k]) { klein= A[i] ; gross= A[k]; } else { klein= A[k]; gross= A[i]; }

    if (klein<min) min= klein;

    if (gross>max) max= gross;

    ++i; --k; }

Du erkennst die 3 if-Befehle, in denen die Elemente miteinander verglichen werden. Die Schleife benötigt \(\left\lfloor\frac n2\right\rfloor\) Schritte. Das gibt \(3\left\lfloor\frac n2\right\rfloor\) Vergleiche.

Comments

omg danke hast mir geholfen