Effektivitetsanalyse
Posted: 27/01-2009 10:26
Heisann, jeg har store problemer med å løse denne oppgaven. Klarer det rett og slett ikke. Her er teksten og selveste oppgaven. Hvis dere svarer på denne tråden, prøv også å forklare på best mulig måte hva dere har gjort.
La oss anta det foreligger en algoritme for et spesielt problem der n (positivt heltall) er et mål for størrelsen på problemet. Tidsforbruket t(n) til algoritmen er derfor avhengig av n. t(n) er av orden høyst f(n) hvis det fins positive konstanter C og N slik at t(n) ≤ Cf(n) for alle n ≥ N. I stor O-notasjon er skrivemåten t(n) = O(f(n)). f(n) kalles ofte for vekstfunksjonen. Det betyr at når n ≥ N vil grafen til t(n) ligge under grafen til Cf(n).
Følgende kan vises:
O(k(f(n)) = O(f(n)), her er k er en positiv konstant
O(f(n)) + O(g(n)) = O(f(n) + g(n))
O(f(n))O(g(n)) = O(f(n)g(n))
Vi har også at O(k) = O(1), for eksempel O(10000) = O(1)
Følgende nyttige identiteter gjelder:
1 + 2 + 3 + . . . + n-1 + n = n(n + 1)/2 og dermed har vi også
1 + 2 + 3 + . . . + n-2 + n-1 = (n-1)n/2
Eks: Gitt en algoritme som bruker 3n2 + 9n operasjoner, dvs t(n) = 3n2 + 9n.
La oss vise at t(n) = O(n2) ut fra definisjonen over.
Siden 9n ≤ n2 for alle n ≥ 9 har vi at 3n2 + 9n ≤ 4n2 for alle n ≥ 9.
Vi lar f(n) = n2, C = 4 og N = 9. Se definisjon over som er uthevet.
Altså har vi at t(n) = 3n2 + 9n = O(n2).
Kommentar: Vi ser at det er det dominerende leddet (det leddet som vokser raskest når n øker), her n2, som vi angir med O-notasjonen. Det betyr at i oppgaver der vi bare skal angi tidsforbruket til en algoritme uttrykt i O-notasjon behøver vi ikke finne C og N. Men noen ganger der vi skal måle tidsforbruket mer nøyaktig må vi ta hensyn til konstanten i det dominerende leddet + eventuelt de lavere ordens leddene.
Vi må også kjenne til følgende når vi senere skal sammenligne
tidsforbruket til ulike algoritmer:
O(1) < O(logn) < O(n) < O(nlogn) < O(n2 ) < O(n3) < O(2n) < O(n!) < O(nn)
Oppgaven:
Hva er størrelsesorden uttrykt i O-notasjon for algoritmen når tidsfunksjonen er gitt som:
(dvs. vi behøver ikke finne C og N)
i) 4n^2 + 50n – 10
ii) 10n + 4 log2n + 30
iii) 13n^3 – 22n^2 + 50 n + 20
iv) 35 + 13 log2n
Det ser kanskje veldig lett ut for mange, men det er er litt stress for meg...
Setter pris på god hjelp 
La oss anta det foreligger en algoritme for et spesielt problem der n (positivt heltall) er et mål for størrelsen på problemet. Tidsforbruket t(n) til algoritmen er derfor avhengig av n. t(n) er av orden høyst f(n) hvis det fins positive konstanter C og N slik at t(n) ≤ Cf(n) for alle n ≥ N. I stor O-notasjon er skrivemåten t(n) = O(f(n)). f(n) kalles ofte for vekstfunksjonen. Det betyr at når n ≥ N vil grafen til t(n) ligge under grafen til Cf(n).
Følgende kan vises:
O(k(f(n)) = O(f(n)), her er k er en positiv konstant
O(f(n)) + O(g(n)) = O(f(n) + g(n))
O(f(n))O(g(n)) = O(f(n)g(n))
Vi har også at O(k) = O(1), for eksempel O(10000) = O(1)
Følgende nyttige identiteter gjelder:
1 + 2 + 3 + . . . + n-1 + n = n(n + 1)/2 og dermed har vi også
1 + 2 + 3 + . . . + n-2 + n-1 = (n-1)n/2
Eks: Gitt en algoritme som bruker 3n2 + 9n operasjoner, dvs t(n) = 3n2 + 9n.
La oss vise at t(n) = O(n2) ut fra definisjonen over.
Siden 9n ≤ n2 for alle n ≥ 9 har vi at 3n2 + 9n ≤ 4n2 for alle n ≥ 9.
Vi lar f(n) = n2, C = 4 og N = 9. Se definisjon over som er uthevet.
Altså har vi at t(n) = 3n2 + 9n = O(n2).
Kommentar: Vi ser at det er det dominerende leddet (det leddet som vokser raskest når n øker), her n2, som vi angir med O-notasjonen. Det betyr at i oppgaver der vi bare skal angi tidsforbruket til en algoritme uttrykt i O-notasjon behøver vi ikke finne C og N. Men noen ganger der vi skal måle tidsforbruket mer nøyaktig må vi ta hensyn til konstanten i det dominerende leddet + eventuelt de lavere ordens leddene.
Vi må også kjenne til følgende når vi senere skal sammenligne
tidsforbruket til ulike algoritmer:
O(1) < O(logn) < O(n) < O(nlogn) < O(n2 ) < O(n3) < O(2n) < O(n!) < O(nn)
Oppgaven:
Hva er størrelsesorden uttrykt i O-notasjon for algoritmen når tidsfunksjonen er gitt som:
(dvs. vi behøver ikke finne C og N)
i) 4n^2 + 50n – 10
ii) 10n + 4 log2n + 30
iii) 13n^3 – 22n^2 + 50 n + 20
iv) 35 + 13 log2n
Det ser kanskje veldig lett ut for mange, men det er er litt stress for meg...
Setter pris på god hjelp