0 Daumen
451 Aufrufe

Frage:

Hallo, ich bräuchte Hilfe bei dieser Aufgabe. Leider versteh hier nicht mal ganz was die Aufgabe fordert.


Gegeben sei eine Liste \(L\) paarweise verschiedener Integer (nicht unbedingt sortiert), d.h jeder Integer, der in der Liste vorkommt, kommt genau einmal vor. Angenommen Sie haben eine Bibliotheksfunktion median(L), die Ihnen den Median (das mittlere Element nach Sortierung, also das \(len(L)//2\)-kleinste Element von \(L\)) in genau \(|L|\) Schritten berechnet, und welche Sie freundlicherweise verwenden dürfen.

Schreiben Sie eine rekursive Python-Funktion element(L,k), die eine solche obige Liste \(L\) und eine Zahl \(k\) mit \(0 <= k <= len(L)-1\) übergeben bekommt und das \(k\)-kleinste Element in \(\mathcal{O}(|L|)\) berechnet.
Code:

von

1 Antwort

+1 Daumen

Hallo :-)

Stell dir mal folgende Liste als Beispiel vor:

\(L = [3, -7, 33, 77, -1, 0, 10, 9]\)

Das ist eine List aus Integern, wobei jeder Integer nur einmal vorkommt, was in der Aufgabe verlangt wird.

Die Funktion median(L) (die du verwenden darfst und nicht notwendigerweise der entspricht, die du vielleicht aus einer Python-Library kennst) macht nun folgendes:

1.) Sie sortiert deine Liste \(L\) zu einer neuen Liste

\(L'=[-7, -1, 0, 3, 9, 10, 33, 77]\).

Offensichtlich verändert das Sortieren nicht die Länge einer Liste, sodass doch schonmal \(len(L)=len(L')=8\) gilt.

2.) Nun wird aus der Liste \(L'\) das Element aus der Mitte (Indexposition \(len(L)//2=8//2=4\)) ausgegeben. Also wird die Zahl 9 ausgegeben.

Das alles geschieht nach Aufgabenstellung in \(|L|\) (hier konkret in 8) Schritten. Wie das genau passiert, kann dir erstmal egal sein.


Nun zur Funktion element(k, L), die du schreiben sollst. Nutze dafür die oben mitgelieferte Funktion median(L). Die bekommt nach Aufgabenstellung eine Liste \(L\) mit den obigen Eigenschaften übergeben und ein Integer \(k\) im Bereich \(0 <= k <= len(L)-1\). Denk daran, es wird bei \(0\) begonnen zu zählen und es wird bei \(len(L)-1\) aufgehört. So funktioniert nämlich die Indizierung beim Programmieren.

Nehmen wir mal das Beispiel von Oben wieder her:

\(L = [3, -7, 33, 77, -1, 0, 10, 9]\) unsortiert und

\(L'=[-7, -1, 0, 3, 9, 10, 33, 77]\) sortiert.

Nun liegt der Parameter \(k\) hier also im Bereich \(0\) bis \(len(L)-1=8-1=7\). Dann lautet hier zb die \(6.\) kleinste Zahl \(33\), da \(33\) an der Indexposition \(6\) steht (also an \(7.\) Stelle). Oder das \(0.\) kleinste Element ist die \(-7\).

Diese Zahlen zu ermitteln, soll durch Rekursion geschehen, sodass der Aufwand immernoch höchstens in der Größenordnung von \(|L|\) (linearer Aufwand) Schritten liegt. Das soll jetzt nicht heißen, dass du wieder nach genau \(|L|\) Schritten fertig bist. Am Ende zählt hier nur der dominierenste Term der Aufwandfunktion.

So liegt zb \(\log_2(|L|)+|L|\) immernoch in \(\mathcal{O}(|L|)\), da für alle \(n\in \mathbb{N}_{\geq 0}\) auch \(\log_2(n)\leq n\) und somit \(\log_2(n)+n\leq n+n=2\cdot n \in \mathcal{O}(n)\) gilt.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community