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.
