---

Jeg fik givet denne opgave af en bekendt, men min besvarelse var ikke i
overensstemmelse med hans instruktør. Jeg fik dog ikke at vide hvor jeg
begik en fejl, så måske er der en af jer der kan fortælle mig det.

Givet en usorteret list af n elementer, hvor lang tid tager det at
konstruere et rød-sort træ indeholdende de n elementer, udtrykt i
O-notation.

Instruktørs besvarelse:
Det tager O(log n) at indsætte et element i et rød-sort træ af størrelse
n. Det skal gøres n gange: O(n * log n)

Min besvarelse:
I stedet for at regne med den tid det tager at indsætte et element når
træet har n elementer, så regner jeg med den tid det tager at indsætte
et element når træet har j elementer (j = 1...n). Min tanke var nemlig
at det selvfølgelig ikke ville tage log n tid at indsætte det første
element, eller det andet element, osv.
log 1 + log 2 + log 3 + ... + log n =
log(1*2*3*...*n) = log n!
Dvs. O(log n!)

Ved at indsætte nogle tal for n ser det ud til at der gælder:
O(n) < O(log n!) < O(n * log n) for n > 3
Så min "løsning" overholder det man umiddelbart kan forvente, men hvor
er fejlen?

Peter Frederiksen

---

> Instruktørs besvarelse:
> Det tager O(log n) at indsætte et element i et rød-sort træ af størrelse
> n. Det skal gøres n gange: O(n * log n)
>
> Min besvarelse:
> I stedet for at regne med den tid det tager at indsætte et element når
> træet har n elementer, så regner jeg med den tid det tager at indsætte
> et element når træet har j elementer (j = 1...n). Min tanke var nemlig
> at det selvfølgelig ikke ville tage log n tid at indsætte det første
> element, eller det andet element, osv.

Jeg tror at du fejler i O. Det er en øvre grænse for tiden/arbejdet. I
praksis tager første element naturligvis ikke lige så lang tid som sidste
element (hvis n>1), men det giver sig udslag i en konstant faktor du vil
dele med, hvilket ikke vedkommer O.
Strengt taget er O(n^2) jo også korrekt. Det er bare ikke nogen særlig stram
O.

---

Jens wrote:
>>Instruktørs besvarelse:
>>Det tager O(log n) at indsætte et element i et rød-sort træ af størrelse
>>n. Det skal gøres n gange: O(n * log n)
>>
>>Min besvarelse:
>>I stedet for at regne med den tid det tager at indsætte et element når
>>træet har n elementer, så regner jeg med den tid det tager at indsætte
>>et element når træet har j elementer (j = 1...n). Min tanke var nemlig
>>at det selvfølgelig ikke ville tage log n tid at indsætte det første
>>element, eller det andet element, osv.
>
>
> Jeg tror at du fejler i O. Det er en øvre grænse for tiden/arbejdet. I
> praksis tager første element naturligvis ikke lige så lang tid som sidste
> element (hvis n>1), men det giver sig udslag i en konstant faktor du vil
> dele med, hvilket ikke vedkommer O.
> Strengt taget er O(n^2) jo også korrekt. Det er bare ikke nogen særlig stram
> O.
>
>
Jeg er ikke med på hvad det er for en konstant faktor du snakker om, jeg
mener ikke at jeg deler med nogen konstant faktor. Tiden det tager at
indsætte et element er jo netop afhængig af størrelsen på træet, dvs. jo
større træ, jo længere tid tager det at indsætte et element.

Peter Frederiksen

---

Scripsit Peter Frederiksen <peterbf@daimi.au.dk>

> Instruktørs besvarelse:
> Det tager O(log n) at indsætte et element i et rød-sort træ af størrelse
> n. Det skal gøres n gange: O(n * log n)

> Min besvarelse:
....
> Dvs. O(log n!)


> Så min "løsning" overholder det man umiddelbart kan forvente, men hvor
> er fejlen?

Der er ingen fejl. For store n gælder Stirlings tilnærmelse

log n! ~ n*logn - n

og da n forsvinder i forhold til n*logn, er de to svar blot
forskellige måder at notere præcis samme størrelsesklasse.

Normalt foretrækker man dog at skrive O(nlogn) i forhold til
O(log n!), fordi førstnævnte er lettere at sammenligne med andre
kompleksitetsangivelser.

--
Henning Makholm "What has it got in its pocketses?"

---

Henning Makholm wrote:
>
>>Så min "løsning" overholder det man umiddelbart kan forvente, men hvor
>>er fejlen?
>
>
> Der er ingen fejl. For store n gælder Stirlings tilnærmelse
>
> log n! ~ n*logn - n
>
> og da n forsvinder i forhold til n*logn, er de to svar blot
> forskellige måder at notere præcis samme størrelsesklasse.
>
> Normalt foretrækker man dog at skrive O(nlogn) i forhold til
> O(log n!), fordi førstnævnte er lettere at sammenligne med andre
> kompleksitetsangivelser.
>

Ahh, ok. Mine udregninger var jo også mere omstændige, så når det giver
det samme er instruktørens løsning at foretrække.

Tak for hjælpen.

Peter Frederiksen