Op dinsdag 11 december 2001 13:01 schreef kvdveer het volgende:
[..]
Dan snap je het niet goed.
O(log N) is minder dan O(n).
Het inlezen van de woorden alleen al is O(n), dus O(log N) is onmogelijk.
Precies. En ik denk zelf dat je niet het hele algoritme O(n) kunt krijgen. Bij mij gaat het afdrukken van het rijtje woorden dat bij 1 cijfercode hoort in O(n), maar alleen door een handige datastructuur waarvan het vullen in O(n log n) gaat.
even de volgorde:
O(1) - iets dat geen loop vereist
Nee, da's niet waar, er mag best een loop inzitten, maar dan wel 1 met een constate lengte. In principe is iets O(1) als het altijd even lang duurt
(op een constante na), onafhankelijk van de invoer.
O(log N) - iets waar je slechts een deel hoeft te doorlopen. Kan zo snel geen voorbeeld verzinnen
Zie je vaak ook vaak bij recursieve algoritmen (b.v. binary search)
O(n^n) - iets datrecursief een loopje in een loopje vereist.
Meestal praat je hier over O(a^n) met voor a een vaste waarde. Dit zijn de klote problemen, de NP-harde problemen.
stel ik wil iets doen met de array x[0..100]
O(log n): (hierover twijfel ik)
code:
1
2
3
4
5
6
| function z(l,r);
begin
for i:=l..r do
x[i]:=0
z(l+1,r-1);
end; |
Dit is volgens mij gewoon O(n^2), maar dan met een constante die kleiner is dan
nul edit:
één
.
Ik zou zeggen:
code:
1
2
3
4
5
6
7
8
| function z(r);
begin
if r > 1 then
begin
//doe hier iest van O(1)
z(r/2);
end;
end; |
En een voorbeeld van een O(2^n) algotje:
code:
1
2
3
4
5
6
7
8
9
10
11
| procedure bitrij(n);
begin
if n = 101 then
print(array x)
else begin
x[n] := 0;
bitrij(n+1);
x[n] := 1;
bitrij(n+1);
end;
end; |
Aanroepen van bitrij(0) drukt nu alle bitrijen ter lengte 100 af, en dat zijn er 2^100 !!!!
edit:
Fout naampje voor mijn O(2^n) procedure veranderd
Naja, we gaan hier maar niet verder over doordraven. Ik schetste maar ff mijn persoonlijke ervaringen he...
:strip_icc():strip_exif()/u/854/tmp18467.jpg?f=community)
:strip_icc():strip_exif()/u/7491/24.jpg?f=community)
Maar dan willen we wel ff weten welke processor de machine heeft waarop onze code getest wordt 
:strip_exif()/u/3398/rh.gif?f=community)
/u/19474/avatar2015.png?f=community){kind=avatar}
:strip_exif()/u/18993/logo.gif?f=community){kind=logo}
:strip_icc():strip_exif()/u/7418/the_hat_icon.jpg?f=community){kind=icon}
/u/39810/danone.png?f=community)
:strip_exif()/u/26373/anim4.gif?f=community)
. Als je de output naar een file stuurt met een pipe ("GoT_2 < thejuryinput.txt > myoutput.txt") is ie klaar in net geen 50 ms 
...
/u/20796/crop64ea633835d95_cropped.png?f=community)
