DD1320 Tillämpad Datalogi

Föreläsning 4: Komplexitetsanalys, sökning

Utskrift av binärträd: inorder, preorder, postorder
Komplexitetsanalys
Linjärsökning
Binärsökning

FYRVERKERIKONSERT IKVÄLL KL 19-21 PÅ BORGGÅRDEN

Utskrift av binärträd: inorder, preorder, postorder

Om man ska skriva ut alla talen i trädet vill man oftast göra det i så kallad inordning (eng. inorder), dvs från vänster till höger.
Fråga: Hur skriver man ut trädet i inordning?
Rekursivt svar: Först skriver man ut vänsterträdet, sedan rottalet, sist högerträdet.
...men ett tomt träd skriver man inte alls.
Följande funktion gör att write(root) skriver ut 1 17 666 4711 9999 för vårt träd.

#Inordning
    def write(p):
        if p != None:
            write(p.left)
            print p.value
            write(p.right)

Om man kastar om dom tre sista satserna får man ändå ut alla talen på skärmen men i andra ordningar. Preordning (eng. preorder) innebär att rottalet skrivs först, sedan vänsterträdet och sist högerträdet. I vårt exempel blir ordningen 4711 17 1 666 9999.

Om vi återgår till orkesterträdet kan vi se att preordning faktiskt ger vettigare utskrift. Så här blir koden i det fallet.

#Preordning     
    def write(p):
        if p != None:
            print p.value
            write(p.down)
            write(p.right)

Utskriften blir då den naturliga. Om vi för tydlighets skull använder indragning av orden på lägre nivå blir utskriften

    Orkester              
        Blås
            Trä
            Bleck
        Stråk
            Vi
            Va
            Vc
            Kb
        Slag

(Hur gör man för att få dessa indragningar?)

Slutligen kan man skriva ut i postordning (eng. postorder) och det innebär att vänsterträdet skrivs först, sedan högerträdet och sist roten. Det ger 1 666 17 9999 4711 i vårt exempel.

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

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