Java Kann mir jemand O-kakül erklären?
- Ersteller mamnu
- Erstellt am
https://medium.com/@mckenziefiege/arrays-linked-lists-and-big-o-notation-486727b6259b
das ist von post 3, einmal durchlesen, danke.
du gehst ja immer vom schlimmsten Fall aus für die Laufzeit und da wäre einfügen an stelle 1 im array. also k=0 -> O(n)
bei ner liste musst du x mal in der liste nach vorne, da dann neues element erstellen und die links richtig setzen, also brauchst du da k schritte, du gehst aber wieder vom schlimmsten fall aus und k = n -> o(n)
wie gesagt, die begründung ist naja, aber es ist die korrekte lösung.
steht auch alles in dem link nochmal.
das ist von post 3, einmal durchlesen, danke.
du gehst ja immer vom schlimmsten Fall aus für die Laufzeit und da wäre einfügen an stelle 1 im array. also k=0 -> O(n)
bei ner liste musst du x mal in der liste nach vorne, da dann neues element erstellen und die links richtig setzen, also brauchst du da k schritte, du gehst aber wieder vom schlimmsten fall aus und k = n -> o(n)
wie gesagt, die begründung ist naja, aber es ist die korrekte lösung.
steht auch alles in dem link nochmal.
Einfügen ist ja dann immer O(n) beim Array, oder außer man macht das eingefügte als letztes Element, oder?
Ich muss dann schon O(n) verwenden oder? Ich könnte ja auch an letzter Stelle was einfügen, dann wäre es doch O(1)
Ich muss dann schon O(n) verwenden oder? Ich könnte ja auch an letzter Stelle was einfügen, dann wäre es doch O(1)
Aber ich könnte es doch an der letzten Stelle auch einfügen, dann wäre es doch O(1) steht doch auch so in der Tabelle
Einfügen an der Position k < n in eine Listenstruktur von n Elementen, implementiert als:
Einfügen an der Position k < n in eine Listenstruktur von n Elementen, implementiert als:
- Array (unter Erhalt aller bereits existenten Einträge. Nehmen Sie an, dass am Ende des Arrays noch leere Einträge existieren.):
wenn array voll, dann könntest es nicht verschieben.. dann bräuchtest ein neues array das eins größer ist, das ist wohl damit gemeint
und da steht ja du sollst es an stelle k einfügen, und k soll < n sein .. somit kannst es nie an letzter stelle einfügen 🙈
und du nimmst auch nie den besten Fall, sondern den schlechtesten um O anzugeben.
und da steht ja du sollst es an stelle k einfügen, und k soll < n sein .. somit kannst es nie an letzter stelle einfügen 🙈
und du nimmst auch nie den besten Fall, sondern den schlechtesten um O anzugeben.
Ok, die Antwortmöglichkeit O(n) gibt es aber bei Arrays nicht.
Da gibt es nur O(1)
O(k), O(1-k), O(log n) und O(n-k)
Müsste ja dann O(k) sein, oder?
hier bei der Aufgabe steht noch mitdabei:
Geben Sie die kleinste obere Schranke für die Komplexität der angegebenen Operationen im O-Kalkül an.
Heißt das dann nicht für den besten Fall?
Dachte man kann es auf eine leeren Eintrag verschieben. Ich frag ja nur so blöd, weil ich es gar nicht check
Da gibt es nur O(1)
O(k), O(1-k), O(log n) und O(n-k)
Müsste ja dann O(k) sein, oder?
hier bei der Aufgabe steht noch mitdabei:
Geben Sie die kleinste obere Schranke für die Komplexität der angegebenen Operationen im O-Kalkül an.
Heißt das dann nicht für den besten Fall?
Dachte man kann es auf eine leeren Eintrag verschieben. Ich frag ja nur so blöd, weil ich es gar nicht check
mamnu schrieb:
ja, du willst ein element an k.ter stelle einfügen und k ist < n
dann hast du o(n-k) und das ist wiederum o(n). (du musst n-k elemente eins nach hinten verschieben damit die k.te stelle leer ist und du dort was neues reinschreiben kannst)
versteh nicht was du daran nicht verstehst :/
Ich will wieder die Funktionen zurück, da konnte man wenigstens Zahlen einsetzen.
Ehrlich gesagt ist es für mich gerade als würce ich ein Buch auf schwedisch oder so lesen. Ich versteh nur Bahnhof
Begründung
Array: die verbleibenden n-k Einträge müssen je eine Position nach hinten verschoben werden
einfach verkette Liste: die Position k durch iterieren (n Schritte) durch die Listenstruktur gesucht werden muss.
doppelte verkette Liste wie einfach verkette, oder?
Ehrlich gesagt ist es für mich gerade als würce ich ein Buch auf schwedisch oder so lesen. Ich versteh nur Bahnhof
Begründung
Array: die verbleibenden n-k Einträge müssen je eine Position nach hinten verschoben werden
einfach verkette Liste: die Position k durch iterieren (n Schritte) durch die Listenstruktur gesucht werden muss.
doppelte verkette Liste wie einfach verkette, oder?
War mir nicht sicher ob n oder k Schritte, aber hab das auch nur aus deinen Begründungen herausgelesen, da wäre ich niemals selber draufgekommen:
Erweitern der Kapazität der Listenstruktur und anschließendes Einfügen eines Elements am Ende der Listenstruktur (wenn die Listenstruktur aus n Elementen besteht und eine maximale Kapazität von m = n Elementen hat).
Wenn die Listenstruktur implementiert ist als:
Erweitern der Kapazität der Listenstruktur und anschließendes Einfügen eines Elements am Ende der Listenstruktur (wenn die Listenstruktur aus n Elementen besteht und eine maximale Kapazität von m = n Elementen hat).
Wenn die Listenstruktur implementiert ist als:
- Array: O(n+1)--> O(n)
weil: eine neue Listenstruktur angelegt werden muss und dort alle n Elemente hineinkopiert werden müssen - einfach verkettete Liste (ohne tail-Referenz): O(n)
weil zuerst alle n Elemente der Listenstruktur kopiert werden müssen und anschließen durch iterieren über n Elemente die Einfügeposition gesucht werden muss. - doppelt verkettete Liste: O(1)
weil mithilfe der tail Referenz das neue Element direkt am Ende der Listenstruktur eingefügt werden kann
R
RalphS
Gast
Du mußt Dir halt im Klaren darüber sein, daß das aber auch gar nichts mit "Praxis" zu tun hat. Es ist pure Theorie. Wenn einer mit "JAVA" kommt, dann hat es schon nichts mehr damit zu tun.
Kleinste obere Schranke deswegen, weil man mehr oder weniger jede Funktion mit O(2^n) abschätzen kann. Das wäre eine triviale Lösung ohne jede Aussagekraft.
Es ist völlig legitim, bei konkret dem ersten Element in einer Liste nach der Implementierung zu fragen. Deswegen gibt es auch die Einschränkung nach nur zulässigen Werten. Ansonsten könnte man in O(1) einfach sagen, Feld 0 ist ungültig. Da Liste, wäre das nächste Feld dann das (erste) gültige.
Eine Liste ist aber ein eindimensionales Objekt. Damit ist die Laufzeit zunächst erstmal irgendwie linear.
Fürs erste Element darf argumentiert werden, daß nicht nach dem Element gesucht werden muß. Wäre das anders, kämen ggfs. noch Suchalgorithmen mit rein und dann würde es interessant werden.
Der Rest ist pures Überlegen und ggfs. etwas Kreativität. WAS muß ich mit meiner Liste machen, um mein Ziel zu erreichen? Muß ich mir alle Elemente einmal angucken? O(n). Muß ich mir eine feste Anzahl von Elementen angucken? O(1). Muß ich mir Elemente MEHRMALS angucken? Dann muß ich bissel weiter überlegen, wie das "mehrmals" genau aussieht.
Wenn ich eine simple Liste hab - nicht verkettet -- und ich soll das ERSTE Element wegwerfen und darf aber keine ungültigen Werte haben, dann muß ich notwendigerweise alle Elemente durchgehen. Üblicherweise kopiert man dazu die Liste und läßt das erste Element weg => O(n). KÖNNTE man Elemente einfach "ungültig" deklarieren, wäre es O(1).
Wenn ich aber eine VERKETTETE Liste hab, dann muß ich ein bißchen den Kopf anstrengen.
Gelingt es mir, Pointer so elegant zu setzen, daß das Element "automatisch" rausfällt? Dann hab ich gute Chancen, O(n) zu unterbieten. Ansonsten hab ich O(kn) für verkettete Listen, Konstanten sind wieder egal, also wie gehabt O(n) im Maximum. (Das k ist hier in bezug auf die Anzahl der Verkettungen.)
Bin ich also in der Lage, die einfach(doppelt) verkettete Liste durch Pointermanipulation in eine neue Liste OHNE das erste Element zu überführen und muß ich dafür nur "so" viele Pointer anfassen, dann hab ich O(1) geschafft. Allerdings muß ich bei "doppelt" verkettet bedenken, daß ich nicht nur einen Pointer ändern muß. Ich muß auch die beiden Pointer des "linken" und "rechten" Elements berücksichtigen und darf dabei auch nicht vergessen, daß auch das ERSTE Element zwei Pointer mitbringt (prev+next) nur daß halt der PREV-Pointer nirgendwohin zeigt, ie NULL ist.
Kleinste obere Schranke deswegen, weil man mehr oder weniger jede Funktion mit O(2^n) abschätzen kann. Das wäre eine triviale Lösung ohne jede Aussagekraft.
Es ist völlig legitim, bei konkret dem ersten Element in einer Liste nach der Implementierung zu fragen. Deswegen gibt es auch die Einschränkung nach nur zulässigen Werten. Ansonsten könnte man in O(1) einfach sagen, Feld 0 ist ungültig. Da Liste, wäre das nächste Feld dann das (erste) gültige.
Eine Liste ist aber ein eindimensionales Objekt. Damit ist die Laufzeit zunächst erstmal irgendwie linear.
Fürs erste Element darf argumentiert werden, daß nicht nach dem Element gesucht werden muß. Wäre das anders, kämen ggfs. noch Suchalgorithmen mit rein und dann würde es interessant werden.
Der Rest ist pures Überlegen und ggfs. etwas Kreativität. WAS muß ich mit meiner Liste machen, um mein Ziel zu erreichen? Muß ich mir alle Elemente einmal angucken? O(n). Muß ich mir eine feste Anzahl von Elementen angucken? O(1). Muß ich mir Elemente MEHRMALS angucken? Dann muß ich bissel weiter überlegen, wie das "mehrmals" genau aussieht.
Wenn ich eine simple Liste hab - nicht verkettet -- und ich soll das ERSTE Element wegwerfen und darf aber keine ungültigen Werte haben, dann muß ich notwendigerweise alle Elemente durchgehen. Üblicherweise kopiert man dazu die Liste und läßt das erste Element weg => O(n). KÖNNTE man Elemente einfach "ungültig" deklarieren, wäre es O(1).
Wenn ich aber eine VERKETTETE Liste hab, dann muß ich ein bißchen den Kopf anstrengen.
Gelingt es mir, Pointer so elegant zu setzen, daß das Element "automatisch" rausfällt? Dann hab ich gute Chancen, O(n) zu unterbieten. Ansonsten hab ich O(kn) für verkettete Listen, Konstanten sind wieder egal, also wie gehabt O(n) im Maximum. (Das k ist hier in bezug auf die Anzahl der Verkettungen.)
Bin ich also in der Lage, die einfach(doppelt) verkettete Liste durch Pointermanipulation in eine neue Liste OHNE das erste Element zu überführen und muß ich dafür nur "so" viele Pointer anfassen, dann hab ich O(1) geschafft. Allerdings muß ich bei "doppelt" verkettet bedenken, daß ich nicht nur einen Pointer ändern muß. Ich muß auch die beiden Pointer des "linken" und "rechten" Elements berücksichtigen und darf dabei auch nicht vergessen, daß auch das ERSTE Element zwei Pointer mitbringt (prev+next) nur daß halt der PREV-Pointer nirgendwohin zeigt, ie NULL ist.
Ist das so jetzt richtig?
Erweitern der Kapazität der Listenstruktur und anschließendes Einfügen eines Elements am Ende der Listenstruktur (wenn die Listenstruktur aus n Elementen besteht und eine maximale Kapazität von m = n Elementen hat).
Wenn die Listenstruktur implementiert ist als:
Erweitern der Kapazität der Listenstruktur und anschließendes Einfügen eines Elements am Ende der Listenstruktur (wenn die Listenstruktur aus n Elementen besteht und eine maximale Kapazität von m = n Elementen hat).
Wenn die Listenstruktur implementiert ist als:
- Array: O(n+1)--> O(n)
weil: eine neue Listenstruktur angelegt werden muss und dort alle n Elemente hineinkopiert werden müssen - einfach verkettete Liste (ohne tail-Referenz): O(n)
weil zuerst alle n Elemente der Listenstruktur kopiert werden müssen und anschließen durch iterieren über n Elemente die Einfügeposition gesucht werden muss. - doppelt verkettete Liste: O(1)
weil mithilfe der tail Referenz das neue Element direkt am Ende der Listenstruktur eingefügt werden kann
R
RalphS
Gast
Du mußt halt genau vor Augen haben, was ein abstrakter Datentyp - Liste unverkettet, einfach, zweifach -- ermöglicht. Üblichweise bringen die ihre eigenen Anforderungen mit, sagen wir INSERT geht für Datentyp X mit O(1), aber DELETE braucht O(n).. dann mußt Du Dir das zusammenstückeln.
Hier im Beispiel (append element to list) würde ich vorsichtig sagen
unverkettet => O(n) weil erst ans Ende der Liste gesucht werden muß, dann Element hinten dran => plus O(1), also O(n)
einfach verkettet => dasselbe über die Pointer => O(n) plus Element dran plus zwei Pointer setzen (vorletztes Element auf das neue, im letzten auf NULL ==> konstanter Aufwand => O(n) total
zweifach verkettet frag ich mich grad ganz besorgt wo Du da eine Tailref her hast. Zumindest nach meinem Verständnis gibt es nur einen Forward-Pointer und einen Reverse-Pointer, sprich ich hab drei Elemente A, B und C
und dann hat
A einen Reversepointer von NULL (erstes Element) und einen Forwardpointer auf B als nächstest
B einen Reversepointer auf A als vorheriges Element und einen Forwardpointer auf C als nächstes
C einen Reversepointer auf B als vorheriges Element und einen Forwardpointer von NULL weil letztes Element.
Komm ich jetzt mit einem D daher, muß ich im Normalfall die Liste durchgehen, wo mein Forwardpointer denn NULL ist, damit ich da das D eintragen kann; sprich ich fange irgendwo an (normalerweise am Anfang) und hangel mich an den Forwardpointern lang. Das dauert O(n).
Hab ich nach n Schritten forward===NULL gefunden, dann kommt nur noch lokale Arbeit:
Forwardpointer von C auf D setzen (bisher: NULL)
Reversepointer von D auf C setzen (neu)
Forwardpointer von D auf NULL setzen (neu)
unabhängig davon, wieviele Einträge schon in der Liste waren, sprich total immer noch O(n).
Aber keine Gewähr. Möglicherweise sind noch weitere Annahmen zu treffen bzgl. der Pointerinhalte, evtl darf ich mein Ende-Element schneller als linear finden, aber das erfordert dann besondere Eigenschaften irgendwo. Ich kann zB auch einen btree auf einem Array implementieren und dann brauch ich nicht O(n) für die Suche. Für btree reicht doppelt verkettet (left child, right child) aber es gibt eine zusätzliche Eigenschaft über die Kettenglieder und ich denke nicht, daß man die hier schon anwenden kann.
Demgegenüber sieht halt das VORNE Einfügen anders aus. Ich kann nicht einfach vorne was dran klatschen, jedenfalls nicht bei einer unverketteten Liste; wenn ich das versuche, hab ich keinen Weg vom neuen ersten Element zum nächsten. Also muß ich die alte Liste an mein neues Element explizit anhängen und dazu muß ich alle Elemente angucken.
Hab ich hingegen eine verkettete Liste, dann hab ich exakt dieses Problem nicht. Ich kann ja den Pointereintrag setzen und kann so einfach aufs alte erste Element verweisen.
Zweifach verkettet und ich muß mir die ersten beiden Elemente angucken, aber nur die ersten beiden, keine anderen: ich muß im neuen Element sagen "reverse = NULL und forward = bisheriges erstes Element" und muß im bisherigen alten Element den Reversepointer auf mein eben eingefügtes Element setzen. Der ganze Rest bleibt erhalten. Der Aufwand ist also konstant.
Naja, zumindest in meinen Augen.
Hier im Beispiel (append element to list) würde ich vorsichtig sagen
unverkettet => O(n) weil erst ans Ende der Liste gesucht werden muß, dann Element hinten dran => plus O(1), also O(n)
einfach verkettet => dasselbe über die Pointer => O(n) plus Element dran plus zwei Pointer setzen (vorletztes Element auf das neue, im letzten auf NULL ==> konstanter Aufwand => O(n) total
zweifach verkettet frag ich mich grad ganz besorgt wo Du da eine Tailref her hast. Zumindest nach meinem Verständnis gibt es nur einen Forward-Pointer und einen Reverse-Pointer, sprich ich hab drei Elemente A, B und C
und dann hat
A einen Reversepointer von NULL (erstes Element) und einen Forwardpointer auf B als nächstest
B einen Reversepointer auf A als vorheriges Element und einen Forwardpointer auf C als nächstes
C einen Reversepointer auf B als vorheriges Element und einen Forwardpointer von NULL weil letztes Element.
Komm ich jetzt mit einem D daher, muß ich im Normalfall die Liste durchgehen, wo mein Forwardpointer denn NULL ist, damit ich da das D eintragen kann; sprich ich fange irgendwo an (normalerweise am Anfang) und hangel mich an den Forwardpointern lang. Das dauert O(n).
Hab ich nach n Schritten forward===NULL gefunden, dann kommt nur noch lokale Arbeit:
Forwardpointer von C auf D setzen (bisher: NULL)
Reversepointer von D auf C setzen (neu)
Forwardpointer von D auf NULL setzen (neu)
unabhängig davon, wieviele Einträge schon in der Liste waren, sprich total immer noch O(n).
Aber keine Gewähr. Möglicherweise sind noch weitere Annahmen zu treffen bzgl. der Pointerinhalte, evtl darf ich mein Ende-Element schneller als linear finden, aber das erfordert dann besondere Eigenschaften irgendwo. Ich kann zB auch einen btree auf einem Array implementieren und dann brauch ich nicht O(n) für die Suche. Für btree reicht doppelt verkettet (left child, right child) aber es gibt eine zusätzliche Eigenschaft über die Kettenglieder und ich denke nicht, daß man die hier schon anwenden kann.
Demgegenüber sieht halt das VORNE Einfügen anders aus. Ich kann nicht einfach vorne was dran klatschen, jedenfalls nicht bei einer unverketteten Liste; wenn ich das versuche, hab ich keinen Weg vom neuen ersten Element zum nächsten. Also muß ich die alte Liste an mein neues Element explizit anhängen und dazu muß ich alle Elemente angucken.
Hab ich hingegen eine verkettete Liste, dann hab ich exakt dieses Problem nicht. Ich kann ja den Pointereintrag setzen und kann so einfach aufs alte erste Element verweisen.
Zweifach verkettet und ich muß mir die ersten beiden Elemente angucken, aber nur die ersten beiden, keine anderen: ich muß im neuen Element sagen "reverse = NULL und forward = bisheriges erstes Element" und muß im bisherigen alten Element den Reversepointer auf mein eben eingefügtes Element setzen. Der ganze Rest bleibt erhalten. Der Aufwand ist also konstant.
Naja, zumindest in meinen Augen.
