Föreläsning 3 Komplexitetsanalys, sökning, rekursion
Komplexitetsanalys, sökning, rekursion
- Komplexitetsanalys
- Linjärsökning
- Binärsökning
- Testning
- Rekursion
Komplexitetsanalys
Det är intressant att se tidsåtgången för en algoritm. Denna anges ofta som funktion av indatas storlek, som av tradition kallas n. Exempel: För sortering är n antalet tal som ska sorteras.
Hur växer tidsåtgångenT(n) för växanden?
T(n)= n |
n | log(n) | n*log(n) | n2 | 2n |
10 | 10 s | 1 s | 10 s | 100 s | 17 min |
100 | 100 s | 2 s | 3 min | 2 tim | 1022 år |
10000 | 10000 s (ca 3 tim) | 4 s | 11 tim | 3 år |
Vi analyserar oftast värsta fallet (det är i regel enklare att räkna på) men man kan också räkna på medelfallet.
Istället för att ange den exakta tidsfunktionen T(n) nöjer vi oss med att ange ordoklassen O(n).
Definition
T(n) är O(F(n)) om det finns positiva konstanter c och n0 sådana att 0<=T(n)<=cF(n) för n>=n0
Vad innebär detta?
- cF(n) anger en övre gräns förT(n) dån är stort.
- Vi behöver bara ta bara med den term som växer snabbast.
- Vi kan bortse från multiplikation med konstant.
- Det spelar ingen roll vilken logaritm vi använder.
Exempel: T(n) = 10n2 + 100n + 10logn + 1000 säger vi är O(n2).
- För små indata är analys onödig - använd den enklaste algoritmen!
- Inläsning från fil tar längre tid än åtkomst av redan inlästa värden.
- Minnesåtgång kan också vara relevant.
Uppgift: Matrismultiplikation
Vad är komplexiteten för matrismultiplikation?
Sökning
Förutsättningar:
- Vi söker efter något element i en lista med n element.
- Det element vi söker efter karakteriseras av en söknyckel (eng key) men kan också ha andra data.
Frågor:
- Vad ska hända om det sökta elementet inte finns med?
- Kan det finnas flera element med samma nyckel? Vill man isåfall hitta alla?
Linjärsökning (Sequential search)
Algoritm:
- Sök igenom elementen i tur och ordning.
- Bryt när det sökta elementet påträffas eller när det uppenbaras att det sökta elementet inte finns med.
Linjärsökning ärO(n) (i värsta fallet måste vi titta på alla n elementen).
Här följer en funktion för linjärsökning i en lista.
def linjarsokning(listan, nyckel): for x in listan: if x == nyckel: return True return False |
Binärsökning
Om listan är sorterad är den snabbaste sökningsalgoritmen binärsökning. Algoritm:
- Beräkna intervallets mittpunkt.
- Avgör om det sökta elementet finns i första eller andra halvan och fortsätt söka där.
11 | 13 | 13 | 20 | 22 | 25 | 28 | 30 | 31 | 32 | 32 | 48 | 62 |
11 | 13 | 13 | 20 | 22 | 25 |
20 | 22 | 25 |
25 |
Binärsökning är O(log n) i värsta fallet:
Vi söker bland n element och undrar hur många varv sökningen kan ta. Antal element att söka bland halveras i varje varv, så första varvet får vi n/2, andra varvet n/4, tredje varvet n/8. Vi är klara när det bara finns ett element kvar att titta på och då är n/2x=1 där x är antal varv. Vi två-logaritmerar bägge led och får att x=2log(n).
Här följer en funktion för binärsökning:
def binsok(listan, nyckel): """Söker i "listan" efter "nyckel". Returnerar True om den hittas, False annars""" vanster = 0 hoger = len(listan)-1 found = False while vanster <= hoger and not found: mitten = (vanster + hoger)//2 if listan[mitten] == nyckel: found = True else: if nyckel < listan[mitten]: hoger = mitten-1 else: vanster = mitten+1 return found |
Testning
Binärsökning är en knepig algoritm att implementera korrekt. Hur testar vi att koden ovan fungerar?
Här är några förslag! Testa:
- normalfallet, t ex att söka efter 14 i listan [9, 14, 23, 54, 92, 104]
- att söka efter ett tal som inte finns med, t ex 15
- att söka i en tom lista []
- att söka efter vänstraste elementet 9 ...
- ... och högraste elementet 104.
- att söka efter ett element bortom vänstra gränsen, t ex 8 ...
- ... och bortom högra gränsen, t ex 105.
Interpolationssökning
är en variant av binärsökning, där man, istället för att välja mittpunkten som nästa sökpunkt, beräknar en bättre gissning.
gissning = low+(item-a[low])/(a[high]-a[low])*(high-low)
Interpolationssökning vara lämplig om:
- Söknycklarna är jämnt fördelade över intervallet.
- Varje jämförelse är extra tidskrävande.
Antalet jämförelser i medeltal blir i så fall O(loglog(n)), men i värsta fallet blir sökningen linjär, dvs O(n).
Rekursion
Rekursiv kommer från latinet och betyder återlöpande. Om man i definitionen av ett begrepp använder begreppet självt så är definitionen rekursiv. Rekursiva tankar kan också användas för problemlösning.
- Rekursiv tanke: reducerar problemet till ett enklare problem med samma struktur
- Basfall: det måste finnas ett fall som inte leder till rekursivt anrop
Sifferexempel
Triangeltalet S(N) är summan av de N första heltalen. S(4)=1+2+3+4
Fråga: Vad är värdet på S(N)?
Rekursivt svar: S(N) = S(N-1) + N ... men S(1)=1.
Här följer en rekursiv funktion för beräkning av triangeltalen:
def S(n): if n == 1: return 1 else: return S(n-1) + n
Fråga: Vilken siffersumma har heltalet n?
Rekursivt svar: Sista siffran plus siffersumman om man stryker sista siffran i n, ...men noll har siffersumman noll.
def siffersumma(n): if n == 0: return 0 return (n%10) + siffersumma(n/10)
Fråga: Hur många siffror har heltalet n?
Rekursivt svar: En siffra mer än om man stryker sista siffran i n, ...men tal mindre än tio är ensiffriga.
def antalsiffror(n) if n
...
Hur fungerar det?
När man skriver egna rekursiva funktioner bör man lita på att det rekursiva anropet fungerar - man behöver inte analysera anropsgången för varje fall. Men för att förstå varför rekursion kan vara extra minneskrävande är det vara bra att känna till hur programspråken hanterar rekursiva anrop.
- För varje anrop skapas en aktiveringspost som innehåller data för anropet, t ex parametrar, lokala variabler och anropspunkt.
- Aktiveringsposten pushas på en stack.
- När det rekursiva anropet är klart poppas aktiveringsposten från stacken, varefter föregående anrop ligger överst på stacken.
s(0) |
s(1) |
s(2) |
s(3) |
s(4) |
huvudprogram |
Rekursiv binärsökning
Binärsökning är lätt att göra rekursivt! Basfallet är att listan är tom, dvs har noll element. Rekursiv binärsökningsfunktion:
def binsok(listan, nyckel): if len(listan) == 0: return False else: mitten = len(listan)//2 if listan[mitten] == nyckel: return True else: if nyckel < listan[mitten]: return binsok(listan[:mitten], nyckel) else: return binsok(listan[mitten+1:], nyckel)
Bedräglig rekursiv implementation av binärsökning
Följande implementation av binärsökning ser ut att fungera. Det har ett testfall som ger rätt resultat. Implementationen är dock fel. Funktionen är inte tillräckligt testad.
def binsok(listan, nyckel):
"""Letar i "listan" efter "nyckel" och returnerar platsen om den hittas, annars -1.
>>> l1 = [1, 3, 5, 7, 9, 11, 13, 15]
>>> where = binsok(l1, 3)
>>> where
1
"""
if len(listan) == 0:
return -1
else:
mitten = len(listan)//2
if listan[mitten] == nyckel:
return mitten
else:
if nyckel < listan[mitten]:
return binsok(listan[:mitten], nyckel)
else:
return binsok(listan[mitten+1:], nyckel)
För att testa koden kan man använda doctest eller skriva några hårdkodade tester. T.ex.
def testcode():
l1 = [1, 3, 5, 7, 9, 11, 13, 15]
where = binsok(l1, 3)
if where == 1: # 3 on place 1 (0-indexed list)
print("SUCCESS: expected 1 got 1")
else:
print("ERROR: expected 1 got " + str(where))
Tester
Testet sätter upp testdata, utför testet och jämför utfallet med ett förväntat resultat. Ovanstående test är otillräckligt.
Några saker att minnas
- En rekursiv funktion kan alltid omformuleras utan rekursion, men om det finns flera rekursiva anrop i funktionen kan det vara besvärligt.
- För många problem är en rekursiv funktion mycket enklare att formulera och ger kortare kod än utan rekursion. Ofta måste man gå via den rekursiva lösningen i tanken även om man gör en icke-rekursiv lösning.
Dålig rekursionslösning
Ett klassiskt exempel på en dålig rekursionslösning är följande implementation av Fibonaccitalen (där varje tal är summan av de två föregående Fibonaccitalen).
def fib(a):
""" returns the fibonaccinumber a
>>> fib(0)
0
>>> fib(1)
1
>>> fib(2)
1
>>> fib(3)
2
>>> fib(4)
3
>>> fib(5)
5
>>> fib(6)
8
"""
if a <= 1:
return a
else:
return fib(a-1) + fib(a-2)