O-Notation

[julia123]

hi, hab noch eine letzte Frage

Ich soll das nach Effiziens sortieren, steht in der O-Notation.:
n*log n , n^2,1, n^n,n

hab es so sortiert:
n^n,n^2,n*logn,n,1

dann hab ich aber überlegt das n^n ja nicht plynominal lösbar ist hab es dann nach hinten veschoben also so:
,n^2,n*logn,n,1,n^n
und dann wusste ich das der Merge-sort n*logn ist und Selektion-Sort n^2 , Aber Mergesort ist schneller, hab das ganze dann so angepasst;
1,n,n*logn,n^2,n^n,

beste grüße

 

[sheel]

Die letzte Zeile ist genau richtig.

Für solche Schulaufgaben (nicht allgemein, weil eigentlich falsch)
als Faustregel, falls man sich schwer tut: Eine hohe Zahl (zB. 1000) für n einsetzen,
alles ausrechnen, und dann nach Größe ordnen (kleinstes zuerst)

1, n, n*logn, n^2, n^n
1, 1000, 3000, 1000000, 10^3000 (besser nicht ausschreiben)
Ist schon nach Größe geordnet, also stimmts.

(für log hab ich den Zehnerlogarithmus genommen, also 10^3=1000
Falls ihr es eher mit dem Zweierlog macht ists auch kein Problem für die Größenordnung)