Föreläsning 3: Komplexitetsanalys, sökning, rekursion

Komplexitetsanalys
Rekursion
Rekursiva dumsvar
Rekursiva anrop
Sifferexempel
Listexempel
Hur fungerar det?
När fungerar det dåligt?

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)	n²	2ⁿ
10 s	1 s	10 s	100 s	17 min
100 s	2 s	3 min	2 tim	10²² år
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 n₀ sådana att 0<=T(n)<=cF(n) för n>=n₀
Vad innebär detta?

cF(n) anger en övre gräns för T(n) då n är stort.
När vi anger ordoklassen kan vi bortse från multiplikation med konstant.
Vilken logaritm menas med log i O(logn)? Som multiplikation med konstant.
Vi tar bara med den term som växer snabbast.

Exempel: T(n)=10n² + 100n + log₁₀n+1000 säger vi är O(n²).

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 intressant.

Uppgift: Matrismultiplikation

Vad är komplexiteten för matrismultiplikation?

Sökning

Förutsättningar:

Vi söker efter något element i en array (vektor) 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 heltalslista.

def linearsearch(tal, vektor):
    for i in vektor:
        if i==tal:
            return 1
    return 0

Binärsökning

Om arrayen ä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.

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/2^x=1 där x är antal varv. Vi två-logaritmerar bägge led och får att x=²log(n).

Här följer en funktion för binärsökning:


def binarysearch(key, vector):
    left=0
    right=len(vector)-1

    while left <= right:
        middle = (left+right)//2
        if key < vector[middle]:
            right=middle-1
        elif key > vector[middle]:
            left=middle+1
        else:
            return vector[middle]
    return -1

Rekursion

Rekursiv kommer från latinet och betyder återlöpande. Definitioner kan vara rekursiva; till exempel kan man definiera begreppet "avkomling" som "barn eller avkomling till barn". Men 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

Rekursiva dumsvar

Nästa övning ägnas åt begreppet rekursivt anrop, alltså när en funktion anropar sej själv. Det påminner om när man i vardagslivet besvarar en fråga på ett sätt som framtvingar en liknande fråga som i sin tur besvaras på ett sätt som framtvingar en liknande fråga etc. Exempel:
Fråga: Hur många år fyller du i år?
Rekursivt svar: Ett år mer än i fjol.
Om man ger sådana dumsvar blir man inte populär, men faktum är att det går utmärkt att programmera på det sättet. Dock måste man se till att rekursionen avslutas när man kommer ner till något enkelt basfall. I mitt fall skulle jag behöva komplettera dumsvaret så här:
...men år 1975 var jag noll år.

Med koden nedan skulle anropet age(2006) ge värdet 31.

   def age(year);
     if year==1975: return 0
     else: return 1+age(year-1)

Rekursiva anrop

Många undrar hur datorn gör när den får fram värdet 31 i exemplet ovan. Egentligen ska man inte bekymra sej om det! Om den rekursiva tanken är korrekt, så kommer datorn att räkna fram rätt värde. Men för den som envisas med att vilja veta vad som händer kommer här den sanna beskrivningen.

Anropet age(2006) ger så småningom upphov till anropet age(2005). Då avbryts tillfälligt exekveringen av age(2006) och en kopia av age trollas fram och börjar exekvera. Kopian har en egen variabel year som sätts till 2005, allt medan original-ages year fortsätter att vara 2006. Så småningom har 31 olika age anropats och alla är tillfälligt avbrutna i väntan på att den anropade kopian ska komma tillbaka med ett siffervärde. Och det 32:a anropet, age(0) returnerar verkligen genast värdet 0. Då kan den sista age slutföra beräkningen 1+0 och returnera värdet 1, etc. Slutligen kan original-age returnera värdet 31 till huvudprogrammet, som inte har någon aning om hur mycket arbete som skett bakom kulisserna!

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
      return s(n-1) + n

Listexempel

Vi tänker oss en länkad lista av objekt, där varje objekt innehåller ett tal och en next-pekare. Variabeln top pekar på den översta posten.
Fråga: Hur många noder finns i stacken?
Rekursivt svar: En nod mer än i stacken under topposten ...men en tom stack har noll poster.

    def antal(p):
      if p is None: return 0
      return 1+antal(p.next)

Anropet antal(top) ger nu rätt svar!

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

Aktiveringsposterna tar extra minne i anspråk och stackhanteringen tar extra tid, så den extremt sparsamme skriver om sina rekursiva funktioner. Vi andra nöjer oss med kompilatorns optimeringar!

När fungerar det dåligt?

Det finns fall där en rekursiv lösning inte lämpar sig. Ett exempel är Fibonaccitalen.

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.

Månad	0 (nov)	1 (dec)	2 (jan)	3 (feb)	4 (mar)	5 (apr)	6 (maj)	7 (jun)	8 (jul)	9 (aug)
Kaninpar	0	1	1	2	3	5	8	13	21	34

    def fib(n):
      if n<=1: return n
      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:

    def fib(n):
      f0=0
      f1=1
      for i in range(n-1):
	f2=f1+f0
	f0=f1
	f1=f2
      return f1

Den här implementationen går i linjär tid, O(n).

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.