---

Hvis man i et udtryk kun beholder det led som har den højeste orden vil:

x^2 + a*x+b

blive reduceret til x^2

Men hvad med:

cx log x + cx

hvor c er en konstant?

---

Hejsa!

Fra 0 til 1/e er c*x størst... fra 1/e til uendelig er cx log x størst!

mvh Kenneth

bunallo wrote:
> Hvis man i et udtryk kun beholder det led som har den højeste orden vil:
>
> x^2 + a*x+b
>
> blive reduceret til x^2
>
> Men hvad med:
>
> cx log x + cx
>
> hvor c er en konstant?
>
>
>

---

> cx log x + cx
> hvor c er en konstant?

En konstant ignoreres i O- theta og omega-notation, hvis du taler om
væksthstighed for tidsforbrug for en algoritme.
Her er største del x.

---

"Jakob Nielsen" <a@a.a> skrev i en meddelelse
news:cv1cb6$179e$1@news.cybercity.dk...
> > cx log x + cx
> > hvor c er en konstant?
>
> En konstant ignoreres i O- theta og omega-notation, hvis du taler om
> væksthstighed for tidsforbrug for en algoritme.
> Her er største del x.

Hvis man ser bort fra c så vil x log x ligger over x efter en vis værdi for
x på min grafregner. Så er det ikke x log x der er den største del??

---

> Hvis man ser bort fra c så vil x log x ligger over x efter en vis værdi
> for
> x på min grafregner. Så er det ikke x log x der er den største del??

Ups. Ser nu at der stod cx log x + cx. og ikke log x+cx.
Så er det naturligvis x log x der er din asymptotiske funktion.

Nu ved jeg stadig ikke i hvilken sammenhæng du taler om væksthastighed. Er
det i datalogisk sammenhæng?
Hvis det er, og du ønsker theta-notationen, så gælder det at en konstant
ganget på din vækstfunktion altid skal ligge over din funktion fra en vis
værdi, og en anden konstant ganget på, altid skal ligge under din funktion,
fra en vis værdi.

hvis f(x) er din funktion cx*log x+cx så vil din vækstfunktion være
g(x) = x*log x
Det gælder at c1*g(x) <= f(x) <= c2*g(x)
Altså.. der findes to konstanter c1 og c2, som ganget på g(x) vil udspænde
et område hvori f(x) altid findes - fra en given x og frem.
Det betyder oftest at f(x) kan gå udenfor det udspændte område i starten,
men fra en eller anden x-værdi vil f(x) aldrig forlade området.
For de fleste algoritmer (ex sortering) vil man ofte opleve at de små
konstanter, og mindre led, for små x betyder en større køretid end den
asymptotiske funktion siger. Der er dog en eller anden x fra hvilken g(x)
kan indeholde f(x) for alle x >= denne grænse.

O-notationen siger kun at der findes en c1 hvor det gælder at c1*g(x)>=f(x).
Omega-notationen er omvendt. c1*g(x)<=f(x)

Håber det var det du ville vide...?