Opened by [E|B] at 2004-07-28 15:51
User since
2003-08-04
771 Artikel
HausmeisterIn
![[Homepage]](/battie/theme/default/homepage.gif)
![[default_avatar]](/battie/theme/default/default_avatar.gif)
2003-08-04
771 Artikel
HausmeisterIn
Jup. Relavant für die Definition ist auch zu wissen, daß konstannte Vorfaktoren egal sind. Zudem sollte man sich genau überlegen, was mit n gemeint ist - meistens die Eingabelänge.
Ein Beispiel, wo man das beides nicht vergessen sollte: der 'schnellste' bekannte Primzahltest geht mit O(n^6). Gemeint ist natürlich die Anzahl der bits und nicht die Zahlengröße. Zudem braucht dieser Test aufm 1GHz-er zum Beweis, daß 13 ne Primzahl ist ca. eine Sekunde. Nichts desto trotz, ist er bei einer 100 000 000 000 000-bit - Primzahl natürlich schneller, als alle anderen bekannten.
Ein Beispiel, wo man das beides nicht vergessen sollte: der 'schnellste' bekannte Primzahltest geht mit O(n^6). Gemeint ist natürlich die Anzahl der bits und nicht die Zahlengröße. Zudem braucht dieser Test aufm 1GHz-er zum Beweis, daß 13 ne Primzahl ist ca. eine Sekunde. Nichts desto trotz, ist er bei einer 100 000 000 000 000-bit - Primzahl natürlich schneller, als alle anderen bekannten.
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}
"":"\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}