Hvorfor er O(t(n)*b^t(n)) = 2^O(t(n))?

Mener du ikke O(t(n)*b^t(n)) = O(b^t(n))??
Det er fordi b^t(n) løber meget hurtigere end t(n) og egentlig fortæller mere om performance en t(n).

I eksemplet sidst i dette indlæg kan du se, at det kun er b^t(n), der bidrager til den mærkbare vækst og t(n) fremstår som en konstant.

Med O notation, er konstanter underordnet, fordi vi kun er interesseret i performanceudviklingen som funktion af elementer og ikke den faktiske tid, en operation tager:
O(1000*n) = O(n)


Væksteksempel hvor 1000 <= t(n) <= 1010:
b = 2

t(n) = 1000
O(t(n)*b^t(n)) = 1,0715086071863E+304
O(b^t(n)) = 1,0715086071863E+301

t(n) = 1001
O(t(n)*b^t(n)) = 2,1451602315869E+304
O(b^t(n)) = 2,1430172143725E+301

t(n) = 1002
O(t(n)*b^t(n)) = 4,2946064976026E+304
O(b^t(n)) = 4,2860344287451E+301

t(n) = 1003
O(t(n)*b^t(n)) = 8,5977850640626E+304
O(b^t(n)) = 8,5720688574901E+301

t(n) = 1004
O(t(n)*b^t(n)) = 1,721271426584E+305
O(b^t(n)) = 1,714413771498E+302

t(n) = 1005
O(t(n)*b^t(n)) = 3,445971680711E+305
O(b^t(n)) = 3,4288275429961E+302

t(n) = 1006
O(t(n)*b^t(n)) = 6,8988010165081E+305
O(b^t(n)) = 6,8576550859921E+302

t(n) = 1007
O(t(n)*b^t(n)) = 1,3811317343188E+306
O(b^t(n)) = 1,3715310171984E+303

t(n) = 1008
O(t(n)*b^t(n)) = 2,765006530672E+306
O(b^t(n)) = 2,7430620343968E+303

t(n) = 1009
O(t(n)*b^t(n)) = 5,5354991854128E+306
O(b^t(n)) = 5,4861240687937E+303

t(n) = 1010
O(t(n)*b^t(n)) = 1,1081970618963E+307
O(b^t(n)) = 1,0972248137587E+304

En lille rettelse - det reducerede udtryk er som du siger:
T(n) = O(n*b^n) = O(2^n)

b skal også betragtes som en konstant, da det er irrelevant hvor hurtigt performance falder og det kan bevises at f.eks. 2^n = 4^(n/2).

/1

O(t(n)*b^t(n)) = 2^O(t(n)) udtrykket er taget direkte fra et bevis på side 260 i bogen "Introduction to the Theory of Computation".

Med andre ord - Uanset hvor hurtigt t(n) vokser (Om det er O(n^2) eller bare O(n)), gælder det at O(t(n)*b^t(n)) = 2^O(t(n)).
Jeg kan bare ikke forstå hvorfor det er sådan.
Du siger at 2^n = 4^(n/2). Hvordan hjælper det i udtrykket?
Det er klart at O(t(n)*b^t(n)) => 2^O(t(n)) - Men hvorfor er der lige netop sat dette loft?

I 2^n = 4^(n/2) er n/2 n ganget med en konstant (1/2). Da konstanter er ligegyldige, kan det reduceres til 2^n = 4^n og also x^n = y^n. Derfor kan man benytte 2^n til at beskrive performance (ligesom b^n, 12^n, osv. vil være lige gyldige).

Jeg skal ikke kunne sige, hvorfor de smider 2^ uden for funktionen..

Ah, ja - Nu forstår jeg. Mange tak :)
Vil du sende et svar, så jeg kan give dig point?

Svar :)

Jeg regnede med, at jeg ville begynde på datalogistudiet til september. Jeg er ikke længere så sikker, når jeg ser på det der. *skræmt*

Det skal du ikke være. Nu skal jeg ikke kunne udtale mig om datalogi (er selv lige blevet færdig som IT ingeniør), men O notation er en meget lille del af studiet, og det er egentlig ikke så svært.

Hvis du f.eks. vil indsætte et element til sidst i en liste:
O(1) fordi tiden det tager ikke afhænger af, hvor mange elementer der allerede er i listen.

Hvis du vil finde noget i en liste, skal du søge hele listen igennem:
O(n) fordi der er n elementer

Man kan lave lister, der har andre O værdier:
HashMap: O(1)
Sorteret liste: O(log2(n))
Eller som i dette eksempel (selvom det nok ikke er en liste): 2^O(t(n))

Ud fra dette kan du så vælge den bedste løsning til dit problem. Hvis listen er lille, kan du overveje at benytte en liste men 2^O(t(n)), men ved større lister, skal du måske overveje et HashMap med O(1).

Men som sagt er det en meget lille del af studiet, som du ikke skal være bange for.

/1