Hast du dazu Referenzen? Hier behauptet der erste Poster, der Aufwand waere sogar O(n), und der Antwortende behauptet, es waere O(1).

Wen genau meinst du mit erster Poster und Antwortende?

Ich sehe niemanden, der behauptet hätte, die Laufzeit wäre in O(1). (Naja, außer - alle Probleme sind von O(1), denn es gibt bestimmt ein n, was so groß ist, daß all unsere Probleme kleiner sind ;) )

Oh, man - wir sollten mal das Design unserer Links ändern. Hab nicht gemerkt, daß das 'hier' ein Link war.

Im _ungünstigsten_ Fall hat man O(n) - schon klar. Die wahrscheinlichkeit dafür, daß ein Hash maximal ungünstig ist, wäre schonmal verdammt klein (ca. 1/n^n, glaub ich), abgesehen davon nimmt Perl eine Umordnung vor, wenn ein Hash beginnt ungünstig angeordnet zu werden. Und O(1) hat man nur im Falle der günstigsten Anordnung, allerdings ist der Aufwand für eine Optimale Anordnung enorm. Und bei einer halbwegs vernünftigen Anordnung kommst du eben im Schnitt auf O(log n) (Man halte sich immer bewusst, daß Hashes eine sehr heuristische Angelegenheit sind). Und mit Optimierungen bekommst du höchstens deine Konstannte runter, nicht dein Laufzeitverhalten besser.

Und als Beweis der Tatsache diene dir ein ausgiebiger Benchmark.\n\n

<!--EDIT|Ishka|1082647584-->

Du meinst hier O(log n), nicht O(n log n), oder?

in der Tat, danke - ich bessers gleich aus

Hmm, Abigail denkt auch, dass es linear ist: http://www.perlmonks.org/index.pl?node_id=347383

Darf ich mal fragen, was linear ist und was Ishka da meint?

also ob so ein algorithmus linear oder quadratisch ist, darueber mache ich mir erst dann gedanken, wenn die moeglichkeit besteht, dass da sehr viele daten kommen; bei 1-1000 daten lohnt es sich in der regel nicht...

anmerkung zur Laufzeit: bubblesort muesste z.B. fuer kleine datenmengen i.d.R. schneller sein als quicksort, weil er weniger overhead hat...

Die Landau-symbole (O, o, Theta, ...) unterliegen folgender Motivation:

- Suchen kompakte Notation zur Aufwandsabschatzung von Algorithmen.
- Algorithmus soll von Problemgrößen abhängen (z.B.: n = Zahl der zu sortierenden Objekte in einer Liste)



Läuft in genau n Schritten ab; wobei n = scalar @array ist; und überschreitet nie die Zahl n; also O(n)

Okay... wenn also was in O(n) läuft, läuft es linear;
O(1) heißt konstant; O(log n) heißt dann logarithmisch und O(n^2) heißt quadratisch



Sei n = scalar @array und m = scalar @brray, dann ist die Laufzeit O(m * n), weil du m mal das @array durchläufst
wenn m == n gilt, dann ist die Laufzeit O(n^2) und wenn
m = n^2 ist, dann wäre die Laufzeit O(n^3)...

Da Plus, Minus, Mal, Geteilt Funktionen sind, die so schnell ausgeführt werden können, dass man deren Laufzeitverhalten unter den Tisch fallen lässt (Sind Funktionen, die in Konstanter Zeit ausgeführt werden können, also O(1) und n*1 = n), wäre man jetzt eigentlich fertig.


Aber wie sieht es hiermit aus?



Eigentlich hat dies auch die Laufzeit O(n), aber nur unabhängig von der Funktion calc...

calc könnte so aussehen


Okay, print vernachlässigen wir wieder, obwohl eine Ausgabe schon zeit kosten kann, aber md5 ist nicht gerade flink.

Also, kann man hier nicht mehr von O(n) sprechen, da man die Laufzeit von md5 auf einen String der länge length($var) * 10000 berücksichtigen muss. Verstanden?

Um nochmal zum Hash zurück zukommen.
Für den Benutzer wirkt die Laufzeit von $hash{$key} Konstant; also O(1)...

In Perl selber muss aber noch eine Operation ausgeführt werden, damit der Wert, der dem Schlüssel zugeordnet ist, gefunden werden kann.

O(Ausdruck(n)) bedeutet, es gibt eine Konstante k, so dass die Laufzeit des Algorithmus für alle n unter k * Ausdruck(n) bleibt.

Das k darf aber auch 42 Trilliarden komma fünf sein.