Übersicht der Komplexitäten von Standard-ADTs gesucht
-
Hallo
Ich suche eine gute Zusammenfassung die Aufschluss darüber gibt, welche Operation von welchem ADT welche Komplexität besitzt.
Z.B. das anfügen eines Elements an einer Liste, das auslesen eines Elements aus einer Queue usw. Für die gängigsten abstrakten Datentypen.
Auch interessant wäre sowas für Such- und Sortieralgorithmen. Also Bubblesort braucht O(n^2) usw.
Und dann noch eine konkrete Frage:
Wenn ein rekursives Modul mit dem Parameter n sich immer selbst mit n % modulo "konstante" aufruft, was ist das für eine Komplexität? Abbruchbedingung ist n kleiner 5.
Ich würde jetzt sagen O(2), wirklich begründen könnte ich's nicht. Mein Versuch: Im idealfall wäre es O(1), da es keinen Rest gibt und somit nach einem Aufruf mit 0 abgebrochen wird. Je nach Größe der Zahl könnte aber einmal ein Rest bleiben der aber beim 2. Aufruf dann auch 0 wird.
-
O(2) ist das gleiche wie O(1). Aber deswegen ist deine analyse trotzdem noch nicht richtig... wenn die funktion nicht spätestens beim zweiten aufruf direkt terminiert (wg. parameter kleiner 5) dann terminiert sie garnicht.
-
Jester schrieb:
O(2) ist das gleiche wie O(1). Aber deswegen ist deine analyse trotzdem noch nicht richtig... wenn die funktion nicht spätestens beim zweiten aufruf direkt terminiert (wg. parameter kleiner 5) dann terminiert sie garnicht.
hm aber wenn ich n % konstante mach (die konstante ist übrigens 6), dann bekomme ich ja entweder 0 oder einen Rest. Der Rest ist in jedem Falle kleiner als die Konstante.
Damit ruft sich die Funktion wieder auf.
Wenn n <5 ist wird terminiert.
Passiert dies nicht wird der Rest % Konstante als neues n übergeben, was ja immer 0 ergibt, oder seh ich das falsch?
-
a % b == (a % b) % b % b ....
-
Oh mist ich dachte
5%6=0
dabei ist das ja 3...
-
Nein, 5.
-
Optimizer schrieb:
Nein, 5.
das kommt davon wenn man nachträglich nur die hälfte an seinem beispiel ändert
Gut, bleibt noch meine Ursprungsanfrage
-
-
Um welche ADTs gehts denn? Queue? Stack? Liste?