Hallo,
ich sitze gerade an einer Algorithmen Übung. Man hat 2 Listen, die beide
sortiert sind, wobei jedes Element nur einmal vorkommt. Nun soll das
k.-größte Element bestimmt werden und zwar in O(log n), mit n der
größten Liste.
Erst einmal etwas grundlegendes. Gibt es einen Trick, aus der
geforderten Komplexität, auf den Algorithmus zu schließen?
Also z.B. bei O(n) ist klar, dass eine Liste Linear durchsucht wird. Bei
O(n*log(n)) denke ich sofort an "teile und herrsche"...Stichwort
Quicksort.
Aber zu O(log(n)) fällt mir im Moment nichts ein.
Wie geht ihr vor, wenn ihr so eine Aufgabe bekommt?
Viele Grüße
Programmierer schrieb:> Erst einmal etwas grundlegendes. Gibt es einen Trick, aus der> geforderten Komplexität, auf den Algorithmus zu schließen?
Manchmal geht das. Man geht die Tabelle der in Frage kommenden
Algorithmen durch und sucht nach einem mit O(log(n)). ;-)
> Also z.B. bei O(n) ist klar, dass eine Liste Linear durchsucht wird.
Denk dran, dass du 2 Listen hast, nicht eine.
Edit: Insbesondere solltest du dran denken, dass die Listen bereits
sortiert sind.
Ja eine binäre Suche habe ich implementiert. Es ist nur die Frage, wie
ich diese jetzt nutzen kann, um das gesuchte Element in beiden Listen zu
finden.
Ich hab die Aufgabenstellung immer noch nicht verstanden.
Im Grunde geht es doch darum, von hinten beginnend in jeder Liste k
Elemente abzuzählen und dann das k-te zu liefern. Denn da die Liste
sortiert ist, muss das dann das k-größte sein.
Annahme: ich weiss, dass die 'Liste' n Elemente groß ist. Und ich
organisiere die Liste als balanzierten binärer Baum. Dann sind die
Knoten 0 bis n/2 im linken Teilbaum und die Knoten n/2+1 bis n im
rechten Teilbaum. Ich muss mich also nur fragen ob mein k größer oder
kleiner als n/2 ist. Wenn größer, dann kann das gesuchte Element nur im
rechten Teilbaum sein. Wenn es kleiner/gleich ist, dann im linken. Und
dort kann ich dasselbe Spiel wieder machen: Ich nehm die Hälfte vom
Intervall und frage mich in welchen der beiden Teile mein gesuchtes
Element liegen wird.
Im Grunde ist das binäres suchen, nur dass ich nicht nach einem
Schlüssel suche, sondern nach der Platznummer.
Wenn man will, kann man das auch so auffassen, dass ich meinen Knoten
einen zusätzlichen Member verpasse, der einfach die Durchnumerierung der
Knoten ist und nach dem ich suche.
Karl Heinz Buchegger schrieb:> Ich hab die Aufgabenstellung immer noch nicht verstanden.
Ich interpretiere es so, dass aus beiden Listen zusammen ein Ergebnis
ermittelt werden soll. Nicht zwei.
> Im Grunde geht es doch darum, von hinten beginnend in jeder Liste k> Elemente abzuzählen und dann das k-te zu liefern. Denn da die Liste> sortiert ist, muss das dann das k-größte sein.
Das wäre dann aber O(k) und nicht als O(f(n)) ausdrückbar.
Über den Begriff "Liste" bin ich aber auch gestolpert. Müsste genauer
spezifiziert sein, was darunter zu verstehen ist. Will hoffen, dass der
Satz oben nicht die ursprüngliche Formulierung ist.
A. K. schrieb:> Karl Heinz Buchegger schrieb:>>> Ich hab die Aufgabenstellung immer noch nicht verstanden.>> Ich interpretiere es so, dass aus beiden Listen zusammen ein Ergebnis> ermittelt werden soll. Nicht zwei.
Dann hab ich die Aufgabenstellung allerdings wirklich nicht kapiert.
Vielleicht wäre ein Beispiel angebracht?
>> Im Grunde geht es doch darum, von hinten beginnend in jeder Liste k>> Elemente abzuzählen und dann das k-te zu liefern. Denn da die Liste>> sortiert ist, muss das dann das k-größte sein.>> Das wäre dann aber O(k) und nicht als O(f(n)) ausdrückbar.
Nicht ganz. Denn wenn es sich tatsächlich im eine vorwärts verkettete
Liste handelt, kannst du die Liste nicht von hinten aufarbeiten, sondern
musst von vorne durchgehen. Und damit sind wir dann wieder beim linearen
"Durchsuchen" von vorne: O(n).
Karl Heinz Buchegger schrieb:> Dann hab ich die Aufgabenstellung allerdings wirklich nicht kapiert.> Vielleicht wäre ein Beispiel angebracht?
Zunächst würde schon der Originaltext weiterhelfen. Denn vor jeder
Lösung steht die Notwendigkeit, überhaupt erst einmal die Frage zu
verstehen. Unzählige Aufgaben werden schon in diesem Stadium versemmelt.
Hier mal ein Beispiel für die Listen:
[1,4,7,9,13]
[2,3,6,8,24,44]
Kannst bitte mal an diesem Beispiel exemplarisch die Geschichte mit dem
Baum erläutern?
Baum ist witzlos, denn der müsste bereits fertig vorliegen, andernfalls
liegt man weit oberhalb von O(n) weil die Reorganisation mitgerechnet
werden muss.
Programmierer schrieb:> Hier mal ein Beispiel für die Listen:>> [1,4,7,9,13]>> [2,3,6,8,24,44]>> Kannst bitte mal an diesem Beispiel exemplarisch die Geschichte mit dem> Baum erläutern?
Wie ist jetzt die Sache mit dem k-größten Element zu verstehen?
Suchst du das k-größte Element, wenn man beide Listen zusammennimmt,
oder das k-größte in der einen Liste und das k-größte in der anderen
Liste? Oder wie ist das zu verstehen.
Konkret: Wenn das 3.-größte Element gesucht wird, was ist dann die
korrekte Antwort in diesem Beispiel?
7, 8, 13?
A. K. schrieb:> Karl Heinz Buchegger schrieb:>>> Dann hab ich die Aufgabenstellung allerdings wirklich nicht kapiert.>> Vielleicht wäre ein Beispiel angebracht?>> Zunächst würde schon der Originaltext weiterhelfen. Denn vor jeder> Lösung steht die Notwendigkeit, überhaupt erst einmal die Frage zu> verstehen. Unzählige Aufgaben werden schon in diesem Stadium versemmelt.
Da hast du recht.
Aber entweder ich sitze jetzt wirklich auf der Leitung oder ich sehs
einfach nicht. Für mich ist die Aufgabenstellung alles andere als klar.
A. K. schrieb:> Über den Begriff "Liste" bin ich aber auch gestolpert. Müsste genauer> spezifiziert sein, was darunter zu verstehen ist. Will hoffen, dass der> Satz oben nicht die ursprüngliche Formulierung ist.
Für eine einfach verkette Liste würd mir einfallen – da eine Liste etwas
"Lineares" ist:
Eine Datenstruktur, bei der
• Es in Zeit O(1) möglich ist, den Nachfolger eines Elements zu finden
• Es in Zeit O(1) möglich ist, den Nachfolger aus der Struktur
zu entfernen
• Es in Zeit O(1) möglich ist, einen Nachfolger hinter ein Element
einzufügen
• Der Verwaltings-Overhead pro Element O(1) ist
Einfach anzunehemn, die Liste sei als balancierter Baum implementiert
oder als Hash-Tabelle etc., find ich geschummelt... Kann aber mitunter
dazu dienlich sein, den Aufgabensteller vorzuführen ;-)
> Konkret: Wenn das 3.-größte Element gesucht wird, was ist dann die> korrekte Antwort in diesem Beispiel? 7, 8, 13?
Na 13.
Du solltest noch mal im Duden nachschlagen was drittgrösst heisst.
Und JA, natürlich ist das eine AUFGABE.
Weil es eben nicht spotteinfach ist, den passenden Algorithmus zu
finden, sondern etwas von der Intelligenz des Befragten abhängt.
Natürlich müsste man in dem Beispiel auch das 4-grösste finden.
Also eine Aufgabenstellung gibt es nicht. Es wurde uns nur gesagt, wer
sich dafür interessiert kann es mal versuchen.
Ich habe mir aber Notizen gemacht.
Demnach ist das Element gesucht, was an k.-Stelle stehen würde, wenn man
beide Liste aneinander hängt und sortieren würde. Ich denke das sollte
jetzt klar sein. Entschuldigung für die eineindeutige Formulierung
meinerseits.
Hallo,
Die Listen sind l und m -elementig.
Die Positon der Einordnung des k.ten Elementes ist in der Gesamtliste
ist in der einen Liste p und in der anderen q.
Programmierer schrieb:> [1,4,7,9,13]>> [2,3,6,8,24,44]
Die 13 stände in Liste 1 mit 5 Elementen an Position 5 und würde in
Liste 2 mit 6 elementen an Position 5 eingefügt werden, welche dann 7
Elemente hätte.
Man muss sich scheinbar darauf einigen, dass das Element einmal
vorhanden, das andere Mal aber eingefügt wird, auch wenn die Listen
doppelte Elemente enthalten sollten (+1).
k wäre dann Position_in_Liste1 (=5-5)+ Position_in_Liste2 (6-5)+1
k wäre also 0+1+1 also das dritte, denn die höchste Position ergibt 0
k= 0 ergibt 44, als Position in Liste 1 = 6, da es eingefügt wird und
Position in Liste 2 = 6, wo es vorhanden ist.
k= 5-6 +6-6 +1 = 0.
Jetzt fehlt nur ein schöner Algorithmus, wie man jetzt binär sucht.
bei k = 2 sucht man
In Liste 1 von li= 5-k= 3 bis re = 5 und in Liste 2 von li= 6-k= 4 bis
re = 6
Nehme ich die Mitte aus Liste 1 [(li+re) / 2 = 4] = 9 findet sich die 9
in Liste 2, wenn sie eingefügt würde an an Position 5.( binäre Suche im
Bereich 4..6 )
k =5-4 + 6-5 +1 = 3, also zu groß.
Also setzte ich links li in Liste 1 auf mitte+1 = 4+1= 5
Der Wert aus Liste 1 ist dann 13 und dieser würde in Liste 2 immer noch
an Position 5 eingetragen.
k= 2 wäre gefunden.
Hätte man es noch nicht gefunden wäre Liste 1 am Ende, dann kann man
sofort aus Liste 2 das (m-k).te Element nehmen.
Man merget die beiden Listen zu einer einzigen sortierten Liste zusammen
und nimmt davon das k.-letzte Element. Natürlich wird nur so viel wie
nötig gemerget, also insgesamt k Elemente. Man braucht aus den gemerge-
ten Elemente auch nicht eine neue Liste bilden, da ja letztendlich nur
eins davon (das k-te) als Ergebnis benötigt wird.
Damit ist die Komplexität von n unabhängig, nämlich O(k). Ist k eine
vorgegebene Konstante, ist die Komplexität sogar O(1).
Dabei bin ich davon ausgegangen, dass der Zugriff auf alle Listenele-
mente in O(1) erfolgt. Sind die Listen nur einfach verkettet, braucht
allein der Zugriff auf das letzte Element schon O(n), weswegen dann
O(log n) nicht realisierbar ist. Bei einfach verkettet Listen wäre es
günstiger, wenn entweder die Listen absteigend sortiert sind oder als
Ergebnis nicht das k.-größte, sonders das k.-kleinste Element gesucht
ist.
Hier ist eine Implementation des im ersten Absatz Geschriebenen in
Haskell (das in C zu programmieren, war ich gerade zu faul ;-)). Da die
Listen in Haskell einfach verkettet sind, wird die k.-kleinste Zahl der
beiden aufsteigend sortierten Listen gesucht. Dass die Komplexität
tatsächlich von der Listenlänge unabhängig ist, sieht man daran, dass
auch unendlich lange Listen in endlicher Zeit bearbeitet werden (letzte
beide Programmzeilen).
Wärs möglich, das Haskell zumindest rudimentär zu kommentieren? Wenn ich
hier mit APL kontern wollte würde mir das vermutlich auch fast niemand
widerlegen und mangels jedweder Schleife oder Rekursion wäre O(1)
garantiert. ;-)
Ich habe freilich den vagen Verdacht, dass dein Beispiel weniger gut
funktioniert, wenn die Listen nicht so schön interleaved sind, sondern
das erste Element von Liste A grösser ist als das letzte Element von
Liste B. Oder sowas in der Art. Was sich zwar mit unendlichen Listen
schlecht machen lässt, wohl aber mit endlichen.
Hallo,
k ist nur ein Bruchteil von n und damit O(k) = O(k/n * n ) = k/n* O(n) =
O(n)
Auch wenn man bei k > n/2 eben nach (n-k) sucht, bleibt es sich gleich.
A. K. schrieb:> Wärs möglich, das Haskell zumindest rudimentär zu kommentieren?
Ich habe mal irgendwo gelesen, Haskell-Code sei selbsterklärend ;-)
Aber eigentlich ist das Verfahren doch naheliegend: Man betrachtet nicht
die kompletten Listen, sondern nur deren paar größte (bzw. kleinste)
Elemente, was ja kein Problem ist, weil die Listen schon sortiert sind.
Insgesamt werden nur k+1 Elemente in die Hand genommen, egal wie lang
die Listen sind.
> Ich habe freilich den vagen Verdacht, dass dein Beispiel weniger gut> funktioniert, wenn die Listen nicht so schön interleaved sind, sondern> das erste Element von Liste A grösser ist als das letzte Element von> Liste B.
Auch dann werden nur k+1 Elemente angeschaut, nämlich k von der einen
Liste und 1 von der anderen.
A. K. schrieb:> Bringt aber nicht weiter weil O(k) komplexer sein kann als O(log n).
Das macht aber nichts, denn es wurde nach einem Algorithmus gefragt,
dessen Rechenzeit bei wachsendem n nicht stärker als log n steigt.
Darüber, wie die Rechenzeit von k abhängt, gibt es keine expliziten
Anforderungen. Man könnte zwar die fehlende Anforderung so interpre-
tieren, dass die Rechenzeit unabhängig von k sein soll, aber das ist
dann wirklich Interpretationssache.
Hallo,
und wenn k immer der Median ist, also bei n/2 steht??
Mein Verfahren macht für jeweilige Listenlänge l = n/2 und der Suche
nach k.tem Element für k = l == Median
1
l~Zugriffe
2
10000108
3
100000163
4
1000000230(100Durchläufe)
5
10000000307(10Durchläufe)
Eine log(n) oder log(k)-Abhängigkeit sehe ich nicht auf Anhieb, ist aber
auch spät.
> Darüber, wie die Rechenzeit von k abhängt,> gibt es keine expliziten Anforderungen.
Doch.
k ist eine zufällig gleichverteilte Zahl aus dem Bereich 1...n.
Damit ist alles was von k abhängt O(n).
Bei solchen Aufgaben wird k immer als Konstante gesehen. Klar, daß k <=
n gilt, aber wenn nach dem drittgrößten Element gesucht in O(log n)
gesucht wird, soll damit ausgedrückt werden, daß hier nur die
Abhängigkeit von n interessiert bei gegebenem, festem k.
Damit paßt schon der Vorschlag, die k größten Elemente aus der kleineren
Liste in die größere Liste jeweils an die korrekte Stelle einzufügen. Da
die Listen sortiert sind, kann dies in O(k*log n) erfolgen. Dann das
k-größte Element aus dieser Liste zurückliefern. Dies kostet O(k). Da k
nun als konstant anzusehen ist, ist das Gesamtergebnis O(k*log n) + O(k)
= O(1 * log n) + O(1) = O(log n).
Wenn die Aufgabenstellung hieße, jeweils das z.B. das k=n-2 größte
Element zu finden, wäre k nicht mehr konstant.
MaWin schrieb:> k ist eine zufällig gleichverteilte Zahl aus dem Bereich 1...n.
Eigentlich 1..2n. Wobei es in dieser Frage nicht auf die statistische
Verteilung ankommt (hier geht es nicht um Statistik), sondern einfach
nur den Wertebereich.
> Damit ist alles was von k abhängt O(n).
Yep, da O(2n)=O(n).
Murkser schrieb:> Klar, daß k <= n gilt
Wieso? Bei zwei gleich langen Listen gibt es 2n Werte und k kann auch
den Wert 2n haben.
> aber wenn nach dem drittgrößten Element gesucht in O(log n)> gesucht wird, soll damit ausgedrückt werden, daß hier nur die> Abhängigkeit von n interessiert bei gegebenem, festem k.
Wenn es von der Anzahl der Gesamtelemente abhängen sollte, dann wäre das
also von maximal 2n, was jedoch immer noch in die gleiche Komplexität
wie O(log n) darstellt. Da ein variables k also nicht in der Komplexität
auftaucht lässt sich aus der Aufgabenstellung nicht schliessen, dass nur
die Abhängigkeit von n interessiert.
A. K. schrieb:> auftaucht lässt sich aus der Aufgabenstellung nicht schliessen, dass nur> die Abhängigkeit von n interessiert.
Korrektur: ... dass k konstant ist..
Guten morgen,
k = konstant für beleibiges n>k ist doch zu nichts nutze.
Das wäre ja O(1/n) für n->unendlich
Alles schon da gewesen, shit.
http://discuss.joelonsoftware.com/default.asp?interview.11.641601.12>kth element in two sorted arrays>> Given two sorted arrays, find the kth element from both of them using only >constant space. Time complexity O(logn^2)http://www.leetcode.com/2011/01/find-k-th-smallest-element-in-union-of.html>;
> O(lg m + lg n)
Wenn n=m= Anzahl der Elemente in einer Liste dann ist, ergibt sich
O(lg m + lg n)= O(lg (m*n))= O(lg( n²))= O(2*lg(n)) = O(log(n))
Das ist ja passend.
Versetzt Euch doch mal in die Rolle des Algorithmen und
Komplexitaetstheorie-Profs, der so eine Aufgabe stellt. Da kommt es
nicht darauf an, ob das zu was nutze ist. Es ist eine Uebungsaufgabe!
Und wenn er sagt, das Problem soll in O(log n) geloest werden, heisst
das wie bei allen aehnlichen Beispielen, die in der Vorlesung so
durchgekaut werden, k darf als konstant angesehen werden. Macht die
Sache nicht komplizierter als noetig.
Wenn es um ein "echtes" Praxisproblem geht, haette der TE (und
derjenige, der die Aufgabe gestellt hat), nicht vorgegeben, dass es in
O(log n) zu loesen sei, sondern er haette gesagt, "mein XYZ Programm
dauert jetzt 10min. Das ist mir zu lang und ich will, dass das in 10s
laeuft".
Hallo,
es ist doch schon längstens für beliebiges 0<k<n entsprechend den
Vorgaben gelöst, was gibt es noch zu diskutieren?
Mit k = konstant macht eine O-Notation gar keinen Sinn, um einen
Algorithmus zu bewerten, indem man einfach gegewn unendlich laufen
lässt.
