DD1320 Tillämpad Datalogi

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

Läs i boken: kap 3 och 4, utom 3.2.3, 3.4.3, 4.3.3, 4.4 (som kommer senare)
Komplexitetsanalys
Linjärsökning
Binärsökning
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ången T(n) för växande n?

	n	log(n)	nlog(n)	n²	2ⁿ
10	10 s	1 s	10 s	100 s	17 min
100	100 s	2 s	3 min	2 tim	10²² å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 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.
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) = 10n² + 100n + ¹⁰logn + 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 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 sequentialSearch(alist, item):
    for x in alist:
        if x == item:
            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.

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 (kursboken s. 146):


def binarySearch(alist, item):
"""Söker i "alist" efter "item". Returnerar True om den hittas, False annars"""
    first = 0
    last = len(alist)-1
    found = False

    while first <= last and not found:
        midpoint = (first + last)/2
        if alist[midpoint] == item:
	    found = True
        else:
            if item < alist[midpoint]:
                last = midpoint-1
            else:
                first = midpoint+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

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

Aktiveringsposterna tar extra minne i anspråk och stackhanteringen tar extra tid, så den extremt sparsamme skriver om sina rekursiva funktioner.

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!

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 (kursboken s. 146):

def binarySearch(alist, item):
    if len(alist) == 0:
        return False
    else:
        midpoint = len(alist)/2
        if alist[midpoint] == item:
            return True
        else:
            if item < alist[midpoint]:
                return binarySearch(alist[:midpoint], item)
            else:
                return binarySearch(alist[midpoint+1:], item)