DD1320 Tillämpad Datalogi
Föreläsning 3: Komplexitetsanalys, sökning, rekursion
- Utskrift av binärträd: inorder, preorder, postorder
- Komplexitetsanalys
- Linjärsökning
- Binärsökning
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
|
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 |
Listexempel
Vi tänker oss en länkad lista av noder, där varje nod innehåller
ett värde och en next-pekare. Variabeln top
pekar på den
översta noden.
Fråga: Hur många noder finns i listan?
Rekursivt svar: En nod mer än i listan under
översta noden ...men en tom lista har noll noder.
def antal(p):
if p is None:
return 0
else:
return 1 + antal(p.next)
Anropet antal(top)
ger nu rätt svar!
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.