DD1320 Tillämpad Datalogi

Komplexitetsanalys, sökning, 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        
1010 s1 s10 s100 s17 min
100100 s2 s3 min2 tim1022 år
1000010000 s (ca 3 tim)4 s11 tim3 å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?


Exempel: 
T(n) = 10n2 + 100n + 10logn + 1000 säger vi är O(n2).




Uppgift: Matrismultiplikation

Vad är komplexiteten för matrismultiplikation?








Sökning


Förutsättningar:


Frågor:





Linjärsökning (Sequential search)

Algoritm:

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:










11131320222528303132324862












111313202225
                            












            202225
                            












                    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:

    

  1.  normalfallet, t ex att söka efter 14 i listan [9, 14, 23, 54, 92, 104]

  2.  att söka efter ett tal som inte finns med, t ex 15

  3.  att söka i en tom lista []

  4.  att söka efter vänstraste elementet 9 ...

  5.  ... och högraste elementet 104.

  6.  att söka efter ett element bortom vänstra gränsen, t ex 8 ... 

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

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









   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)





Några saker att minnas