mboost-dp1
O-notation, worst case?
Hey
Jeg er lige startet (eller, jeg starter i morgen) på algoritmer og datastrukturer.
Jeg har læst i bogen og er stødt på et lille problem. Man kalder store O for worst case, men når man kigger på dette billede, ser man at g ligger over f, og så kan f vel ikke være worst case? Eller har jeg misforstået noget?
Håber nogen kan forklare, ellers må jeg vente til i morgen og se om det går op for mig.
På forhånd tak :)
Mark
Edit: har det noget at gøre med at big O er "tight"? Men så vil der jo ikke være forskel på O og omega
Jeg er lige startet (eller, jeg starter i morgen) på algoritmer og datastrukturer.
Jeg har læst i bogen og er stødt på et lille problem. Man kalder store O for worst case, men når man kigger på dette billede, ser man at g ligger over f, og så kan f vel ikke være worst case? Eller har jeg misforstået noget?
Håber nogen kan forklare, ellers må jeg vente til i morgen og se om det går op for mig.
På forhånd tak :)
Mark
Edit: har det noget at gøre med at big O er "tight"? Men så vil der jo ikke være forskel på O og omega
Ville nok ikke ligefrem kalde asymptotisk og gennemsnitlig for samme ting :)
På det viste billede: f(n) = O(g(n)), betyder bare at der findes konstanter n1 og k, sådan at g(n) * k vil være større end f(n), for alle værdier af n større end n1.
På grafen er der et enkelt peak op hvor g(n) faktisk er lavere. Dette betyder ikke noget da man kun kigger på grænsen (asymptotisk).
På det viste billede: f(n) = O(g(n)), betyder bare at der findes konstanter n1 og k, sådan at g(n) * k vil være større end f(n), for alle værdier af n større end n1.
På grafen er der et enkelt peak op hvor g(n) faktisk er lavere. Dette betyder ikke noget da man kun kigger på grænsen (asymptotisk).
#3
Asymptotisk og gennemsnitlig er slet ikke det samme.
Men det er to helt forskellige aspekter af big O.
Det asymptotiske aspekt er det som goer at kun det mest signifikante led når n går mod uendelig betragtes.
Det gennemsnitlige aspekt er med hensyn til de faktiske data. Et klassisk eksempel er quicksort. Worst case quick sort kræver faktisk n*n operationer, men det betragtes som en n*logn algoritme, da gennemsnittet kræver det antal operationer.
Asymptotisk og gennemsnitlig er slet ikke det samme.
Men det er to helt forskellige aspekter af big O.
Det asymptotiske aspekt er det som goer at kun det mest signifikante led når n går mod uendelig betragtes.
Det gennemsnitlige aspekt er med hensyn til de faktiske data. Et klassisk eksempel er quicksort. Worst case quick sort kræver faktisk n*n operationer, men det betragtes som en n*logn algoritme, da gennemsnittet kræver det antal operationer.
Gå til top
Opret dig som bruger i dag
Det er gratis, og du binder dig ikke til noget.
Når du er oprettet som bruger, får du adgang til en lang række af sidens andre muligheder, såsom at udforme siden efter eget ønske og deltage i diskussionerne.
- Forside
- ⟨
- Forum
- ⟨
- Programmering
Gå til bund