DD1320 Tillämpad Datalogi
Komplexitetsanalys, sökning, rekursion
- Komplexitetsanalys
- Linjärsökning
- Binärsökning
- Testning
- Rekursion
Magnify the Universe
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ången T(n)
för växande n
?
|
            n     |
        log(n)         |
      nlog(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ör T(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 är O(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
Rekursiv bild,
rekursivt recept
Sifferexempel
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<10:
return 1
return 1+antalsiffror(n//10)
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)
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
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)
doctest
Python har inbyggd testfunktionalitet som kallas doctest. Man skriver som man skulle skrivit på kommandoraden.
ICKE-FUNGERANDE REKURSIV IMPLEMENTATION AV BINÄRSÖKNINNG
Testerna nedan fungerar fast koden fungerar inte. Vad bör man testa när man testar sin kod?
"""
Searches for sokt in v and returns index or -1 if not found
v - sorted vector
sokt - element to search for
"""
def binsearch(v, sokt):
"""
>>> v = [2, 4, 5, 6, 9]
>>> binsearch(v, 2)
0
>>> binsearch(v, 5)
2
"""
if len(v) == 0:
return -1
mid = len(v) // 2
if v[mid] == sokt:
return mid
elif (sokt < v[mid]) :
return binsearch(v[0:mid - 1], sokt)
else:
return binsearch(v[mid + 1:len(v)], sokt)
def test_binsearch():
v = [2, 4, 5, 6, 9]
x = binsearch(v, 5)
print ("expected 2, got ", x) # if-sats saknas
def _test():
import doctest
doctest.testmod()
#test_binsearch()
_test()
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.
- Den rekursiva funktionen kräver i regel mer minne (och tar längre tid) än motsvarande icke-rekursiva funktion.