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.
Karl Heinz Buchegger schrieb: > Für mich ist die Aufgabenstellung alles andere als klar. Yep. Deshalb ist das ohne O-Ton bloss Kaffeesatzlesen.
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).
1 | mergeLists [] ys = ys |
2 | mergeLists xs [] = xs |
3 | mergeLists (x:xs) (y:ys) |
4 | | x < y = x : mergeLists xs (y:ys) |
5 | | otherwise = y : mergeLists (x:xs) ys |
6 | |
7 | findKLeast k xs ys = mergeLists xs ys !! (k-1) |
8 | |
9 | main = do |
10 | print $ findKLeast 3 [1,4,7,9,13] [2,3,6,8,24,44] |
11 | print $ findKLeast 7 [1,5..] [2,4..] |
12 | print $ findKLeast 1000000 [1,5..] [2,4..] |
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 | 10000 108 |
3 | 100000 163 |
4 | 1000000 230 (100 Durchläufe) |
5 | 10000000 307 (10 Durchlä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.
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.