Laufzeit eines Algorithmus angeben
-
Wie genau gebe ich die Laufzeit eines Algorithmus an. Damit meine ich Form, Hintergrund, ... eben alles was dazu gehört. Man liest immer so komische Sachen bei Algorithmen (vor allem Sortierverfahren etc.) wie O(n2) oder O(n) oder sogar O(n lg n). Was hat es damit auf sich? Ist eine riesen Wissenslücke bei mir die ich gerne stopfen würde, weil ich nie ne Antwort parat habe wenn einer mit sowas anfängt.
Thanks,
Arthur Dent
-
frag den Reiseführer per Anhalter durch die galaxis. alternativ geht auch die encyclopaedia galactica aber der Anhalter verkauft sicht etwas besser. vorallem weil in grossen freundlichen buchstaben *peep* auf seinem umschlag steht. (erweise dich als würdig, was steht drauf? *g*)
ne aber jetzt mal im ernst. am einfachsten lässt sich das an algorithmen die mit arrays arbeiten erklären. dabei ist N die anzahl der elemente. willst du z.B. das grösste element in einem array finden musst du alle elemente genau einmal betrachten also ist die komplexität O(N). willst du aber sagen wir jede zahl mit jeder andere multiplizieren (wozu auch immmer) dann musst du für jedes element N N multiplikationen durchführen (mit sich selber auch in dem biespiel) also ist die komplexität O(N*N) bzw O(N^2)...
das ist aber in jedem buch über algorithmen 1000 mal besser erklärt als ich das kann... schau also mal am besten in so einem buch nach.mfg japro
-
N ist immer die maximale Anzahl der Elemente, die betrachtet werden können. Bei logarithmischen Angaben lässt man die Basis aus. Konstanten in Multiplikationen fallem ebenfalls immer weg.
O(2 N) entspricht somit O(N)
O(log2 N) entspricht O(log N)Bei einer Addition wird nur der dominatne Teil notiert:
O(N^5 + N^2) wird zu O(N^5)