Sist endret: 17.08.2010

Løsningsforslag - Kjøretidsanalyse

Innleveringsfrist: 07.10.2011 10:00

Du er logget inn og får derfor se om du har svart riktig/feil på de enkelte oppgavene.
LF-svar er markert med grønt og feil svar er markert med rødt.

Hvis dere er uenige i fasit, oppfordres dere til å diskutere dette på algdats nyhetsgruppe. Denne nyhetsgruppen har også et webgrensesnitt.

Oppgave 1

Sett inn det manglende ordet.
Merk at de øvre/nedre begrensningene bare gjelder for n >= n₀ der n₀ er en konstant.

a) At en algoritme har kjøretid O(f(n)), betyr at kjøretiden har en ... begrensning. (2.5 %)

øvre nedre øvre og nedre

Din kommentar:
LF-forklaring:	Kjøretiden er øvre begrenset av c * f(n), hvor c er en konstant.

b) At en algoritme har kjøretid Θ(f(n)), betyr at kjøretiden har en ... begrensning. (2.5 %)

øvre nedre øvre og nedre

Din kommentar:
LF-forklaring:	Kjøretiden er nedre begrenset av c₁ * f(n), og øvre begrenset av c₂ * f(n), hvor c₁ og c₂ er konstanter.

c) At en algoritme har kjøretid Ω(f(n)), betyr at kjøretiden har en ... begrensning. (2.5 %)

øvre nedre øvre og nedre

Din kommentar:
LF-forklaring:	Kjøretiden er nedre begrenset av c * f(n), hvor c er en konstant.

Oppgave 2

Denne oppgaven tar for seg intuitiv forståelse av kjøretiden for gjennomgang av ulike datastrukturer.

Angi alle svar med den asymptotiske notasjonen som gir mest informasjon. Dvs. de fleste kjøretider omfattes av O(nⁿ), siden dette er en veldig høy øvre grense, mens Θ(f(n)) angir både en øvre og nedre grense og gir derfor mye mer informasjon.

a) Hva er tidskompleksiteten for å traversere ei lenka liste med n ulike elementer?
(2.5 %)

T(n)=Θ(1)
T(n)=Θ(log n)
T(n)=Θ(n)
T(n)=Θ(n²)
T(n)=Θ(n³)

Din kommentar:
LF-forklaring:	For å gå gjennom n elementer trenger man maks n operasjoner og minst n operasjoner. Derfor er T(n)=Θ(n).

b) Hva er tidskompleksiteten for å traversere lenkede lister med én milliard elementer?
(5 %)

T(n)=Θ(1000000000)
T(n)=Θ(1)
T(n)=Θ(n)
T(n)=Θ(n log n)
T(n)=Θ(n²)
T(n)=Θ(n^1000000000)

Din kommentar:
LF-forklaring:	For å gå gjennom en milliard elementer trenger man en milliard operasjoner og da en milliard er et konstant multiplikat av 1 er T(n)=Θ(1).

c) Hva er tidskompleksiteten for å traversere ei matrise med n rader og n kolonner?
(2.5 %)

T(n)=Θ(1)
T(n)=Θ(log n)
T(n)=Θ(n)
T(n)=Θ(n log n)
T(n)=Θ(n²)
T(n)=Θ(n³)

Din kommentar:
LF-forklaring:	For å gå gjennom n*n elementer trenger man maks n² og minst n² operasjoner.

d) Hva er tidskompleksiteten for å traversere (gå gjennom alle elementene) en datastruktur med form som det første laget av en klinkekulepyramide (se bilde under), der n=antall rader?
(2.5 %)

T(n)=Θ(n log n)
T(n)=Θ(n * sqrt(n)), der sqrt=kvadratrot
T(n)=Θ(n²)
T(n)=Θ(n²*log n)
T(n)=Θ(n³)
T(n)=Θ(n⁴)

Din kommentar:
LF-forklaring:	Må gå igjennom alle kulene: Sum_i=1ⁱ⁼ⁿ i = n(n+1) / 2 = n/2 + n²/2 Denne summeformelen står på side 111 i Rottmann (1999), en veldig kjekk bok å ha for hånden når du skal regne ut tidskompleksitet

e) Hva er tidskompleksiteten for å traversere (gå gjennom alle elementene) en datastruktur med form som en pyramide (se bilde) med høyde n?
(5 %)

T(n)=Θ(n log n)
T(n)=Θ(n²)
T(n)=Θ(n²*log n)
T(n)=Θ(n²*sqrt(n)), der sqrt=kvadratrot
T(n)=Θ(n³)
T(n)=Θ(n⁴)

Din kommentar:
LF-forklaring:	Sum_i=1ⁱ⁼ⁿ (i/2 + i²/2) = (n(n+1)/2) / 2 + (n(n+1)(2n+1)/6) / 2 = (n/4 + n²/4) + (n/12 + 2n²/12 + n²/12 +2n³/12) = 4n/12 + 6n²/12 + 2n³/12 Merk at det ikke er nødvendig å løse ut parantesene, det holder å se direkte fra summeformelen at n³ blir det dominerende leddet

f) Hva er tidskompleksiteten for en algoritme som ved iterasjon nummer i bruker i² operasjoner? Algoritmen bruker n iterasjoner.
(5 %)

T(n)=Θ(n log n)
T(n)=Θ(n²)
T(n)=Θ(n²*log n)
T(n)=Θ(n²*sqrt(n)), der sqrt=kvadratrot
T(n)=Θ(n³)
T(n)=Θ(n⁴)

Din kommentar:
LF-forklaring:	Dette likner veldig på oppgaven over og kan løses på samme måte. Antall operasjoner blir rekkeutviklingen 1+4+9+....+n^2, som har kjent løsning n(n+1)(2n+1)/6 = (2n^3 + 3n^2 + n)/ 6 som er Θ(n³).

Oppgave 3

Denne oppgaven tar for seg substitusjonsmetoden for å løse rekurrenser.
Gitt rekurrensen
T(n) = 2401T(n/7) + n³
T(1) = 1

Dersom vi skulle benyttet oss av substitusjonsmetoden og antatt at:
T(n/2) <= c * n²/4 * log(n/2)

a) Hva håper vi å kunne bevise? (7.5 %)

At man kan finne en nedre asymptotisk grense for rekurrensen
At T(n) <= c * n²/4 * log(n/2)
At T(n) <= c * n * log(n)
At T(n) <= c * n² log(n)

Din kommentar:
LF-forklaring:	Antagelsen om at T(n/2)<=cn²/4log(n/2) for n/2 impliserer at vi forsøker å bevise at T(n)<=cn²log(n) for n. (Dette ser vi hvis vi erstatter n/2 med n.)

b) Hvis du anvender master-teoremet på denne rekurrensen (se forelesning 5), hvilket tilfelle tilhører den? (2.5 %)

Case 1
Case 2
Case 3
Ingen av dem

Din kommentar:
LF-forklaring:

c) Hva blir kjøretiden? (valgfri fremgangsmåte) (2.5 %)

Θ(n)
Θ(n log(n))
Θ(n²)
Θ(n³)
Θ(n⁴)

Din kommentar:
LF-forklaring:	Masterteoremet case.1: a=7⁴, b=7, f(n)=n³).

d) Hvis vi bytter ut n³ med n⁵ hvilket case får vi da hvis vi vil bruke Master-teoremet? (5 %)

Case 1
Case 2
Case 3
Ingen av dem

Din kommentar:
LF-forklaring:

Oppgave 4

Denne oppgaven dreier seg om variabelskifte. Merk at n^1/2 = √n .

a) Løs rekurrensen gitt ved: T(n) = T(n^1/2) + 1 (10 %)

Θ (lg n)
Θ (lg lg n)
Θ (lg n lg lg n)
Θ (lg lg n lg lg n)

Din kommentar:
LF-forklaring:	La m = lg n og S(m) = T(2^m). Dermed får vi: T(n) = T(2^m/2) + 1, som igjen gir: S(m) = S(m/2) + 1. Denne løser vi enkelt med masterteoremet og får S(m) = Θ(lg m). Setter vi dette inn i den opprinnelige rekurrensen finner vi løsningen: T(n) = T(2^m) = S(m) = Θ(lg m) = Θ (lg lg n).

Oppgave 5

Denne oppgaven handler om rekursjonstrær. Disse kan brukes som et hjelpemiddel for å gjette på en løsning til substitusjonsmetoden. Hver node i et rekursjonstre representerer en kostnad. I figuren under er det et eksempel for rekurrensen T(n) = 2T(n/2) + n, med T(1) = 1.

Eksempel på rekursjonstre

Merk at rekursjonstreet har blitt tegnet trinnvis og at ikke hele er tegnet opp. Å tegne det trinnvis kan være lurt for å klare å se hvordan det fortsetter. I treet over ser vi at den interne kostnaden i hver node vil være n/2ⁱ der i er nivået noden befinner seg på (0-indeksert).

Nivået til løvnodene finner vi ved å løse n/2ⁱ = 1:
log₂ 2ⁱ = log₂ n
i log₂ 2 = log₂ n
i = log₂ n
Antallet noder på hvert nivå ser vi at er 2ⁱ. Antallet løvnoder er altså 2^{log₂ n} = n

a) Gitt rekurrensen T(n) = T(n/3) + T(n/2) + n, T(1) = 1. Hva er høyden til rekursjonstreet? (7.5 %)

Θ(n*log(n))
log₃(n) + 1
log₆(n) + 1
Θ(log(n))
log_3/2(n) + 1

Din kommentar:

LF-forklaring:

T(n/2)-leddet er det dominerende, slik at høyden vil være log₂(n) + 1 (det krever flere delinger for å komme til 0 når du bare deler på 2 enn når du deler på 3).
I asymptotisk notasjon ser vi bort fra konstanter. log_a(n) er bare forskjellig fra log_b(n) med en konstant faktor, log_a(n) = log_b(n)/log_b(a). I alternativene som ikke bruker asymptotisk notasjon, kan vi ikke se bort fra denne konstanten, så de er derfor feil alle sammen. 1-tallet ses bort fra i asymptotisk notasjon fordi det domineres av log n.

Oppgave 6

Funksjonen gjoerNoe() har kjøretid Θ(1).

def f1(i):
    gjoerNoe()
    if i <= 1:
        return
    f1(i // 2)
    f2(i - 2)

def f2(i):
    gjoerNoe()
    if i <= 1:
        return
    f1(i // 2)

a) Hva en kjøretiden til f1(n)? (Tips: Ikke prøv å regne ut nøyaktig.) (15 %)

Θ(log(log(n)))
Θ(log(n))
Θ(sqrt(n))
Θ(n)
Θ(n * log(n))
Θ(n * sqrt(n))
Θ(n²)
Ingen av alternativene over er riktige.

Din kommentar:
LF-forklaring:	T₁(n) = Θ(1) + T₁(n/2) + T₂(n-2), T₁(1) = Θ(1) T₂(n) = Θ(1) + T₁(n/2), T₂(1) = Θ(1) T₁(n) = Θ(1) + T₁(n/2) + Θ(1) + T₁((n-2)/2) = T₁(n/2) + T₁(n/2 - 1) + Θ(1) ca= 2 * T₁(n/2) + Θ(1) Ser at T₁(n) = Θ(n)

Oppgave 7

I denne oppgaven skal du analysere kjøretiden til små funksjoner.funksjonen gjorNoe(n) har kjoretid Θ(n).

def funksjon1(n):
    if n > 0:
        funksjon1(n-42) 
        funksjon1(42)
    gjorNoe(42)

(5 %)

T(n)=O(1)
T(n)=O(n)
T(n)=O(log n)
T(n)=O(n*log n)
T(n)=O(n²)
T(n)=O(n³)
T(n)=O(2ⁿ)
den vil aldri stoppe

Din kommentar:
LF-forklaring:	funksjon1(42) kaller funksjon1(42).

def funksjon2(n):
    gjorNoe(n)
    if n >= 1:
        funksjon2(n//3)
        funksjon2(2*n//3)

(7.5 %)

T(n)=O(1)
T(n)=O(n)
T(n)=O(log n)
T(n)=O(n * log n)
T(n)=O(n²)
T(n)=O(n³)
T(n)=O(2ⁿ)
den vil aldri stoppe

Din kommentar:
LF-forklaring:	Ut fra rekusrjonstreet ser man at det er cn på ethvert nivå og høyden til treet er Θ(log(n)).

def funksjon3(n):
    gjorNoe(n//6)
    if n > 0:
        funksjon3(n/2-2)
        funksjon3(n/2-3)

(7.5 %)

T(n)=O(1)
T(n)=O(n)
T(n)=O(log n)
T(n)=O(n*log n)
T(n)=O(n²)
T(n)=O(n³)
T(n)=O(2ⁿ)
den vil aldri stoppe

Din kommentar:
LF-forklaring:	For store verdier av n kan vi se bort fra -3 og -2 ,dermed kan dette tilnærmes til rekurrensen T(n)=2T(n/2)+Θ(n) som har løsning Θ(nlog(n)) etter case 2 av masterteoremet.