Övning 2
Komplexitet
-
KÖRTIDER
En viss algoritm tar 0.5 ms när antal indata är 100. Hur lång kommer körtiden att bli när antal indata är 500 om man vet att körtiden är:- linjär
- O(NlogN)
- kvadratisk
- kubisk
Linjär \(k*n\)
N = 500 k * 500 = x ------------- N = 100 k * 100 = 1/2 5 x = - = 2.5 ms (5x längre) 2 O(NlogN) k * NlogN N = 500 k * 500 * log(500) = x ------------------------ N = 100 k * 100 * log(100) = 1/2 5 * log(500) x = ------------ = 3.37 ms (6.74x längre) 2 * log(100) kvadratisk k * N * N N = 500 k * 500 * 500 = x ------------------- N = 100 k * 100 * 100 = 1/2 5 * 5 x = ----- = 12.5 ms (25x längre) 2 kubisk k * N * N * N N = 500 k * 500 * 500 * 500 = x ------------------------- N = 100 k * 100 * 100 * 100 = 1/2 5 * 5 * 5 x = --------- = 62.5 ms (125x längre) 2 - Tidstentan 2014-01-08, uppgift 4 (betyg E + C)
-
Betyg E
Antalet binära strängar av längd n är 2n. Antalet alfanumeriska (ca 32 olika tecken) strängar av längd m är 32m.Vad blir uttrycken ovan om n=10 och m=3?
Hur mycket större än m måste n vara för att det första uttrycket ska bli större än det andra?
-
Betyg C
Linda berättar för Alexander att hon bytt till ett lösenord med 45 binära siffror. ''Men herregud!'', säger Alexander, ''Det blir ju alldeles för lätt att knäcka. Själv har jag 9 alfanumeriska tecken i mitt.''Vems lösenord är svårast att knäcka med totalsökning?
Ungefär hur många sekunder tar knäckningen om datorn prövar en miljard lösenord i sekunden?
Visa dina beräkningar!
Binära sökträd
-
-
TRÄDBYGGEN
- Hur ser det binärträd ut som skapas om man puttar in talen 4 2 1 6 3 7 5 i denna ordning?
- Och hur ser det ut om man sätter in dom i omvänd ordning, alltså 5 7 3 6 1 4 2?
- Är båda träden binära sökträd?
- Är de balanserade?
Insättning av 4 2 1 6 3 7 5 ger trädet
4 2 6 1 3 5 7Binärt sökträd: ja
Balanserat: jaInsättning av 5 7 3 6 1 4 2 ger trädet
5 3 7 1 4 6 2Binärt sökträd: ja
Balanserat: ja
-
POSTORDERTRÄD
- Skriv ut något av träden i inordning och bygg upp ett nytt träd från denna talföljd.
- Skriv sedan ut dom i preordning och bygg upp nya träd från dessa talföljder.
- Skriv slutligen ut dom i postorder och bygg upp nya träd från dessa talföljder.
Inordning + nybygge
Båda träden ger 1 2 3 4 5 6 7 8 i inordning
Nya trädet bli en tarm, ytterst obalanserat.1 2 3 4 5 6 7Preordning + nybygge Första trädet i preordning ger 4 2 1 3 6 5 7 och nytt träd blir
4 2 6 1 3 5 7(samma som ursprungsträdet)
Andra trädet i preorder ger 5 3 1 2 4 7 6 och nytt träd blir
5 3 7 1 4 6 2(samma som ursprungsträdet)
Postorder + nybygge
Första trädet i postorder ger 1 3 2 5 7 6 4 och nytt träd blir
1 3 2 5 4 7 6Andra trädet i postorder ger 2 1 4 3 6 7 5 och nytt träd blir
2 1 4 3 6 5 7
Rekursion
-
GCD
För att beräkna största faktorn som två tal m och n har gemensamt kan vi använda Euklides algoritm:
Om m är jämnt delbar med n så är n den största gemensamma faktorn. Annars är GCD(m, n) = GCD(n, m%n). Skriv en rekursiv funktion!
def gcd(m, n): if m%n == 0: return n else: return gcd(n, m % n) -
FIBONACCITAL
Leonardo Fibonacci skrev år 1225 en bok där han beskrev denna intressanta talföljd:
Sista december föds en kaninpojke och en kaninflicka. Vid två månaders ålder och varje månad därefter producerar varje kaninpar ett nytt kaninpar. Vi kan skriva en rekursiv formel för antal kaninpar:\(f(0)=0\)\(f(1)=1\)\(f(n)=f(n-1) + f(n-2)\)
Skriv en rekursiv funktion för att beräkna Fibonaccital. Visa vilka rekursiva anrop den ger upphov till vid beräkningen av f(5). Är det här det effektivaste sättet att beräkna Fibonaccitalen?
def fib(n): if n <= 1: return n else: return fib(n-1) + fib(n-2)
Man kan visa att antalet anrop faktiskt växer snabbare än själva Fibonaccitalen!
(För N=40 är Fibonaccitalet ca hundra miljoner men antalet rekursiva anrop är över 300 miljoner.)
Bättre vore här att använda en for-slinga:
Den här implementationen går i linjär tid, O(n).def fib(n): f0 = 0 f1 = 1 for i in range(n-1): f2 = f1 + f0 f0 = f1 f1 = f2 return f1 -
REKURSIV TRÄDSUMMA
Ge en rekursiv tanke för summan av alla talen i trädet och programmera den så att anropet tree.sum() ger rätt svar.
Rekursiv tanke: Summan är rottalet plus vänsterträdets summa plus högerträdets summa ... men tomt träd har summan noll.
def summa(p): # Om den står utanför klassen slipper man self if p == None: return 0 else: return int(p.value)+summa(p.left)+summa(p.right) class Bintree - - - def sum(self): return summa(self.rot)
-
REKURSIV TRÄDHÖJD
Ge en rekursiv tanke för höjden av ett träd. Höjden är den maximala nivån som nån av trädets noder befinner sig på. Ett träd med bara en rotnod har höjden 0, och ett tomt träd har höjden -1.
Rekursiv tanke: Höjden är 1 + max(höjden av vänsterträdet, höjden av högerträdet) ...men tomt träd har höjden -1.
def height(p): if p == None: return -1 else: h1 = height(p.left) h2 = height(p.right) return max(h1,h2) + 1 - Aliententan 2015-03-20, uppgift 9 (betyg A)
Samtliga solförmörkelsedatum på jorden under perioden 4000 f.kr. - 4000 e.kr. är insorterade i ett binärt sökträd. Givet en historisk persons födelse och död, beskriv en algoritm som hittar antal solförmörkelser personen potentiellt skulle kunna ha upplevt under sin livstid.
Algoritmbeskrivningen måste vara välstrukturerad och begriplig.