public class Oppgave1 { int fib(int tall, String innrykk) { // Skriv ut dette kallet: System.out.println(innrykk+"f("+tall+") ..."); int res; if (tall<2) res = 1; else res = fib(tall-1,innrykk+" ")+fib(tall-2,innrykk+" "); // Skriv ut resultatet: System.out.println(innrykk+"= "+res); return res; }
public static void main(String[] args) { Oppgave1 f = new Oppgave1(); // Kunne vaert static over?? f.fib(5,""); f.fib(6,""); } }
Thomas, her må du legge inn samme som i
file:/net/www/htdocs/ii/undervisning/kurs/h00/i120/losninger/oppgave2/sol2.html
Jeg fant ikke ut hvordan gjøre dette.
R-2.9
Vi må vise
1.f(n)+g(n) er O(max{f(n), g(n)}) og
2.max{f(n), g(n)} er O(f(n)+g(n))
Vi bruker definisjonen på side 47 i læreboka. For både
1) og 2) kan vi velge konstanten n0=1.
For 2) kan vi velge konstanten c=1, da max{f(n), g(n)} <= f(n)+g(n),
om vi antar (naturlig
nok) at f(n) og g(n) begge er positive, for alle n. For 1) velger vi
konstanten c=2, siden
f(n)+g(n) <= 2*(max{f(n), g(n)}). Dvs f(n)+g(n) = 2*(max{f(n), g(n)})
for verdier av n hvor
f(n)=g(n), og ellers er f(n)+g(n) < 2*(max{f(n), g(n)}.
f2 er O(N^2), dvs N i annen. Tildelingen i den indre for-løkken
utføres
1 gang når i=1, 2 ganger når i=2, osv inntil n-1 ganger
når i=n-1.
Kjøretiden totalt blir dermed O(Sum{i=1} til {i=N-1} i)= O(N^2).
f3 er O(N). k starter på 0, øker med 1 hver gang gjennom
while-løkken,
og vi stanser når k=2N-1.
f4 er O(NlogN). Dette er Flettesorteringsalgoritmen.
Analysen kan gjøres ved å se at kallet f4(N) leder til
to kall
f4(N/2) samt O(N) tid for å flytte elementer mellom tabeller
og
kjøre f3. Vi kan sette opp et (binært) tre av rekursive
kall,
som vil ha dybde logN, og se at det i hvert nivå vil utføres
O(N) arbeid.