Java Kann mir jemand O-kakül erklären?

[mamnu]

Hallo,
für Funktionen weiß ich ja was O-Kakül ist, aber wie ich finde ich z.B. bei den folgenden fragen raus, was das passende O-Kakül ist?

Löschen des ersten Elements einer Listenstruktur von n Elementen, implementiert als:

• Array (das an jeder Position nur gültige Elemente enthalten darf!):
• einfach verkettete Liste:
• doppelt verkettete Liste:

Wäre jemand so nett würde mir das mal erklären? Ich bedanke mich schon mal im voraus

 

[Mr.Baba]

stell dir doch einfach vor, dass das löschen des ersten elements eine funktion ist
für funktionen weißt es ja z.B.

bei nem array müsstest n-1 elemente in ein neues array kopieren -> o(n)
bei ner einfach verketteten liste die start adresse auf das zweite element setzen 🤔 -> o(1)
und bei ner doppelt verketteten liste vorher vom zweiten element auf nix, und das zweite element als erstes setzen 🤷‍♀️ -> o(1)
irgendwie strange aufgaben
kannst ja durch logisches denken beantworten, kommt aber natürlich immer bissl auf die implementierung an

 

[E-tech]

Siehe z.B. O-Notation für Array und LinkedList .

Sehr stark vereinfacht: Wie lange benötigst du ein Element am Anfang, Ende, beliebige Position zu entfernen und dabei die Datenstruktur zu erhalten.

 

[pseudopseudonym]

• Array (das an jeder Position nur gültige Elemente enthalten darf!):

O(n), da du das erste Element löscht und alle anderen vorrücken musst. Wie in einer Excel-Tabelle, in der du die erste Zeile löscht und alle anderen von Hand hochschiebst, sodass die erste Zeile nicht frei ist.

• einfach verkettete Liste:

O(1), da du bloß den Verweiß vom Kopf auf das erste Element ändern musst, sodass der Kopf auf das Zweite Element zeigt.
Das zweite Element findest du logischerweise in konstanter Zeit.

• doppelt verkettete Liste:

Hier musst du noch einen zweiten Verweis ändern, was du an der Listenstruktur siehst. Ist aber noch immer konstant, daher O(1).

 

[benneq]

Sehr stark vereinfacht: Wie lange benötigst du ein Element am Anfang, Ende, beliebige Position zu entfernen und dabei die Datenstruktur zu erhalten.

"lange" würde ich in Zusammenhang mit O-Notation nicht verwenden. Das ist ja kein Benchmark, sondern eine Beschreibung der Komplexität. Also eher "wie viele Schritte / Operationen sind nötig". Die O-Notation sagt im Grunde rein gar nichts über die Performance eines Algorithmus aus.

 

[pseudopseudonym]

Die O-Notation sagt im Grunde rein gar nichts über die Performance eines Algorithmus aus.

Bei kleinen Datenmengen vielleicht nicht, bei großen jede Menge.

 

[Mr.Baba]

hmm, doch schon irgendwie.. wenn man n^2 oder n^3 hat, sollte man nicht zu viele elemente haben, weil sonst wohl langsam -> o-notation kann durchaus einiges aussagen über die performance eines algorithmus.

 

[Jesterfox]

Sie sagt nichts über die absolute Performance aus (sieht man ja schon daran das einfach und doppelt verkettete Liste den selben Wert haben), aber wie diese skaliert wenn man die Datenmenge vergrößert.

 

[benneq]

@pseudopseudonym @Mr.Baba
Dann lasst es mich so ausdrücken: Die O-Notation ist ein mathematisches Modell zur Beschreibung der Komplexität von Algorithmen.
Also ja: Wenn ich exakt denselben Algorithmus n^2 vs. n^3 benchmarke, dann stimmt das Ergebnis natürlich mit der O-Notation überein: n^3 ist langsamer als n^2.

Aber: Ein Problem, das sich in n sehr rechenaufwändigen Schritten lösen lässt, ist nicht zwangsläufig schneller als eine Lösung in n^2 simplen Schritten.
Das hängt zum Teil auch stark von unserer Hardware ab - im Speziellen das Prefetching. Hier kann es passieren, dass ein O(n) Algorithmus langsamer läuft als ein O(n^2) Algorithmus, einfach nur, weil im O(n^2) Algorithmus die Reihenfolge der Datenzugriffe besser vorhersehbar ist und dadurch Leerlaufzeit vermieden werden kann.

Parallellisierbarkeit von Algorithmen kann natürlich auch noch einen Unterschied machen. Ist manchmal erst möglich, wenn man den komplexeren Algorithmus wählt, aber dafür kann man sein Problem dann auf hunderte Threads verlagern und so im Endeffekt wieder deutlich schneller zur Lösung kommen.

Ich sage nicht, dass es nie stimmt, sondern dass man sich nicht immer darauf verlassen sollte.

Ich hatte da mal 'nen Talk von der CppCon gesehen, wo das sehr schön vorgeführt wurde. Entweder war's der Talk über das Animation Framework von Chromium oder über die Optimierung von QuickSort in GCC / Clang.

EDIT: Hier ist der Talk:

YouTube

An dieser Stelle steht ein externer Inhalt von YouTube, der den Forumbeitrag ergänzt. Er kann mit einem Klick geladen und auch wieder ausgeblendet werden.

YouTube-Embeds laden

Ich bin damit einverstanden, dass YouTube-Embeds geladen werden. Dabei können personen­bezogene Daten an YouTube übermittelt werden. Mehr dazu in der Datenschutzerklärung.

YouTube-Embeds laden

Datenschutzerklärung

 

[pseudopseudonym]

@benneq
Ist alles nichts neues für mich, dennoch ist es falsch, dass die O-Notation gar nichts über die Performance aussagt.

 

[RalphS]

Die O-Notation ist ein rein theoretisches Modell. Wenn das Ding nichts über die reale Laufzeit eines Algorithmus aussagt, dann hat man falsch abgeschätzt.

Wenn einem der Compiler entgegenkommt und aus dem hundsmiserablen bubblesort etwas macht, was O(nlog(n)) braucht, dann ist das toll, hat aber mit dem Problem nichts zu tun.

In einer Nußschale: Die O-Notation gibt an, in welcher Form die Laufzeit eines Algorithmus von dessen Eingabe abhängt. Nicht mehr, aber auch nicht weniger.

An der Stelle geht sie Hand in Hand mit gewissen zwei anderen Modellen: O ist eine obere Schranke, also haben wir außerdem noch eine abschätzbare untere (langsamer geht nicht) und eine einfassende Schranke (es wird nicht langsamer, aber auch nicht schneller). Für Sortieren gibt es bspw eine untere Schranke größer 1 (nonparallel), man kann nicht in nur einem Schritt sortieren, die Eingabelänge spielt immer eine Rolle.

AUSNAHME bzw erweiternd spielt Parallelität mit rein. Wenn ich bei einer Eingabelänge von n auch eine CPU-Zahl von n hab, dann kann ich in O(1) sortieren.

 

[bog]

mir gefaellt, was meine zwei vorredner geschrieben haben.

im widerspruch zu benneqs beitrag waere noch zu erwaehnen, dass die landau-notation ein abstraktes mittel ist, um algorithmen oder mathematische funktionen zu beschreiben. caches und compiler-optimierung sind gegenstandslose einwuerfe, da ich dir fuer jeden algorithmus der terminiert ab einem gewissen punkt unendlichviele eingaben n konstruieren kann, sodass O(n^2) stets O(n^3) in der laufzeit schlaegt. die endlichvielen eingaben, fuer die O(n^3) schneller als O(n^2) ist, nennt man dann pathologische faelle, und sind fuer die abstrakte aussage der landau-symbole nicht relevant.

fuers formelle empfehle ich den wiki-eintrag zu den landau-symbolen.

 

[mamnu]

Ich glaub ich habe es noch nicht so ganz verstanden mit euren Erklärungen machen die Antworten Sinn, aber wie finde ich den heraus was das richtige O-Kakül ist?

Finden des Medians (= mittleres Element in sortierter Reihung) in einer aufsteigend sortierten Listenstruktur mit n Elementen, implementiert als:

• Array (das an jeder Position nur gültige Elemente enthalten darf!):
• einfach verkettete Liste:
• doppelt verkettete Liste:

Null Plan wie ich es z.B. hier herausfinde

 

[Mr.Baba]

array -> o(1) array[ (int) array.length/2 - 1 ] (manchmal gibt es 2 mittlere elemente )
verkettete liste musst erst mal über alle drüberlaufen um die länge zu bestimmen -> o(n)
doppelt verkettet, dasselbe -> o(n)

ob man noch schritte dazwischen braucht um es formal richtig dazustellen 🤷‍♀️

 

[mamnu]

und wie kommt man jetzt beim array auf O(1)? Mit Funktionen war das leichter, da hat man einfach nur große Zahlen eingesetzt

 

[Mr.Baba]

array[ ( array.length/2 aufgerundet -1 ] -> ein schritt

ich glaub du brauchst das ganze formaler.. kp.. frag deinen tutor?! oder nen komilitonen?!

bei nem array kannst direkt auf jedes element zugreifen, daher 1 schritt
bei ner liste musst über alle elemente laufen um überhaupt erstmal die länge zu bestimmen, da brauchst n schritte
doppelt verkettet heißt nur du kannst vorwärts und rückwärts durch die liste, ändert nichts an o()

 

[mamnu]

Habe ich jetzt ein Denkfehler drin? Aber wenn ich z.B. ein Array
von {1,2,3,4,5}, dann wäre ja die Länge 4
4/2=2
2-1=1
und der Index 1 wäre doch 2 und nicht der eigentliche Median 3, oder?
Ich frag nur kann auch sein, dass ich gerade ein Brett vor dem Kopf habe

 

[Jesterfox]

Die Länge ist aber 5, sind ja auch 5 Elemente drin...

 

[Mr.Baba]

genau erstes element ist an position array[0], zweites element an array[1], und ist doch auch egal, ob /2 +- whatever, ändert nichts am o(1)

Spoiler: wayne

wenn 6, gerade, dann 6/2 = 3 (-1) | 6 elemente, index 2 und 3 wären korrekt
wenn 5, ungerade, dann (int) 5/2 | 5 elemente, index 2

 

[mamnu]

Ich checks irgendwie immer noch nicht ganz bin froh, wenn ich die anderen 2 Aufgaben endlich hinter mir habe
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.): O(1) ist ja nur einfügen, oder? Begründung: Man direkt auf Position k zugreifen kann, oder?
• einfach verkettete Liste: O(1) Begründung: die verbleibenden n - k Einträge im Array um je eine Position nach hinten geschoben werden müssen, oder?
• doppelt verkettete Liste: das gleiche wie bei einfach verketteten?

die verbleibenden n - k Einträge im Array um je eine Position nach hinten geschoben werden müssen.
die verbleibenden k - n Einträge im Array um je eine Position nach hinten geschoben werden müssen.
man direkt auf Position k zugreifen kann.
die Position k durch iterieren (k Schritte) durch die Listenstruktur gesucht werden muss.
die Position k durch iterieren (n Schritte) durch die Listenstruktur gesucht werden muss.
man 1 - k Elemente verschieben muss.

jetzt wollen die auch noch eine Begründung