O(2n) € O(n) € O(1), deshalb ist das nicht genau. Du hast doch angefangen, zu provozieren. Wenn wir uns hier streiten oder auch die Komplexitätstheorie, dann nützt das dem TE/TO gar nix, glaube ich mal. Also mach’ dein Ding, ich versuche meines zu machen. Peace
Nein, O(2n) ist echt gleich O(n). Das geht direkt aus der Definition hervor:
[tex]O(f) = \left{ g : N \rightarrow R | \exist c \in R \gt 0 \exist n_0 \in N \forall n \ge n_0 : g(n) \le c \cdot f(n)\right}[/tex] (wobei N und R die Zahlenmengen darstellen sollen - der \mathbb Befehl funktioniert hier nicht…)
Daran sieht man, dass nur das c sich ändert, wenn f anders ist. Die Mengen sind daher identisch.
Außerdem gilt [tex]O(1) \subset O(n)[/tex] und nicht umgekehrt.
Ich wollte nicht provozieren, sondern hatte deine O-Notation nur nicht verstanden. Daher habe ich nachgefragt.
Meine ich ja, O(2n) = O(n) Ɔ O(1), du hättest die Definition nicht abschreiben müssen, ich benutze übrigens immer Theta, wenn ich genau sein möchte
Ich möchte nicht mit Wissen prahlen, sondern nur nüchtern wiedergeben, was alles an BubbleSort usw. zusammenhängt, wo ist dein Problem, das es hier keine Kekse gibt?
Vermutlich ist dir die Note egal, welche er im Abi bekommt, mir aber nicht, sonst hätte ich nicht versucht, etwas zu schreiben.
Vereinfacht gesagt, enthält O(f)/o(f) alles, was kleiner/wirklich kleiner f ist, deshalb enthält O(n^n) wahrscheinlich fast alles (mit enthält ist Obermenge/wirkliche Obermenge gemeint). Weiteres siehe bitte beim üBerfliegen hier: http://de.wikipedia.org/wiki/Komplexitätstheorie und hier: http://de.wikipedia.org/wiki/Landau-Symbole , denn dort ist wirklich alles korrekt.
handshake?
Wie schon gesagt, Komplexitätstheorie ist mir nicht fremd.
[quote=CyborgBeta;82213]handshake?[/quote]Ich hatte es nie auf Konfrontation abgesehen. Daher: klar.
Allerdings irritieren mich Aussagen wie:
oder
Ja, gut, das waren Sticheleien meinerseits, einfach überlesen
Vielleicht noch mal Maxsort betrachten, man spart sich dabei das “Umverlinken”, wenn ich das richtig sehe, denn das aktuelle Maximum kann in der neuen Liste einfach vorne/hinten angehängt werden - für selsort ist es wahrscheinlich eine schnellere Implementierung