Komplexität von Algorithmen: Komplexität der Form O(N) - #15623 (Allgemeine technische Fragen)

Ishka

2004-07-28 17:02

User since
2003-08-04
771 Artikel
HausmeisterIn

n log n heißt einfach n mal log n

O() ist keine Funktion, sondern eine Klasse (im Prinzip eine Menge), dh. du kannst nicht sagen O() Sekunden. Ein Algorithmus kann halt ein Element dieser Klasse sein. Dadurch weißt du dann, wie er sich verhällt, wenn es viele Eingabewerte werden.

Vielleicht helfen dir ein paar Beispiele weiter:

Code: (dl )

1
2

my $n=...;
for(1..$n){print '.'}

Ist linear in n (dh. O(n)), bzw. exponentiell in der Eingabelänge (irritierenderweise auch als O(exp n) bezeichnet -- das ist das, was ich meinte mit hinschauen, was gemeint ist)

Code: (dl )

1
2

my $n=...;
for(1..$n**2){print '.'}

Ist natürlich quadratisch in n (dh. O(n^2)) -- Eingabelänge lass ich jetzt erstmal weg, um dich nicht weiter zu verwirren

Code: (dl )

1
2

my $n=...;
for(1..$n){algo($n)}

Wobei algo die Komplexität O(n) habe.
Ist natürlich auch Quadratisch, dh O(n^2)

Verständlicher?

sub z{if(@_){1while$x[$k=rand 10];t($t=$x[$k]=1)}print map"$z[$x[$_]]$_".($_%3?
"":"\n"),1..9}sub t{$j=0;$x[$_+1]==$t&&($j+=2**$_)for 0..8;z,die"Gewinner $z[$t]
"if grep$_==($j&$_),7,56,73,84,146,273,292,448;z,die"Gleichstand\n"if@x>9&&!grep
!$_,@x}@x=4;@z=qw{. [ (};z$^T&1;while(<>){next if$_>9||$x[$_];t$t=$x[$_]=2;z 1}