F3 Komplexitetsanalys

Komplexitetsanalys

Sökning

Typkonvertering

Linjärsökning (Sequential search)

Binärsökning

Testning

Testmatris

Klasser i python

Typer i C

Uppgift: Matrismultiplikation

Uppgift: Förbättra funktionen

Komplexitetsanalys
Linjärsökning
Binärsökning
Testning
Typkonvertering.
typer i C

Denna föreläsning handlar om algoritmer. Vi börjar med att titta tillbaka på de två algoritmerna från förra förläsningen, inser och append

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$ $n$ antalet tal som ska sorteras.
Hur växer tidsåtgången $T (n)$ $T\left(n\right)$ för växande $n$ $n$ ?

https://www.desmos.com/calculator Links to an external site.

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)$ $T\left(n\right)$ nöjer vi oss med att ange ordoklassen $O (n)$ $O\left(n\right)$ .

Definition

$T (n)$ $T\left(n\right)$ är $O (F (n))$ $O\left(F\left(n\right)\right)$

om det finns positiva konstanter $c$ $c$ och $n_{0}$ $n_0$ sådana att

$0 \leq T (n) \leq c \cdot F (n)$ $0\le T\left(n\right)\le c\cdot F\left(n\right)$ för $n \geq n_{0}$ $n\ge n_0$

Vad innebär detta?

$c \cdot F (n)$ $c\cdot F\left(n\right)$ anger en övre gräns för $T (n)$ $T\left(n\right)$ då $n$ $n$ är stort.
Vi behöver bara ta bara med den term som växer snabbast.
- Om den snabbast växande termen är som mest ett polynom (t.ex. $n^3$ ) så anses algoritmen kunna utföras av en dator inom en rimlig tid. Exponentiella funktioner kan inte lösas på rimlig tid.
Vi kan bortse från multiplikation med konstant.
Det spelar ingen roll vilken logaritm vi använder.

Exempel:

$T (n) = 10 n^{2} + 100 n + \log_{10} n + 1000$ $T\left(n\right)=10n^2\:+\:100n\:+\:\log_{10}n\:+1000$ säger vi är $O (n^{2})$ $O\left(n^2\right)$

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.

Vad är tidskomplexiteten för matrismultiplikation?

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 i så fall hitta alla?

Den enklaste sökningen: bryter så fort den hittar det sökta elementet.

Algoritm:

Gå igenom varje element i listan:
- Jämför elementet med nyckeln, och
- ...returnera True om dom är lika
Returnera False om hela listan gåtts igenom utan att elementet hittats.

Linjärsökning är $O (n)$ $O\left(n\right)$ (i värsta fallet måste vi titta på alla $n$ $n$ elementen).

Här följer en funktion för linjärsökning i en lista.

def exists(the_list, key):
    for x in the_list:
        if x == key:
            return True
    return False

Den här funktionen talar bara om huruvida elementet finns med i listan. Hur ska den modifieras för att returnera den plats i listan elementet finns?

Om listan är sorterad är den snabbaste sökningsalgoritmen binärsökning. Algoritm:

Beräkna intervallets mittpunkt.
Är det nyckeln? Avbryt, det sökta elementet är funnet.
Annars: Avgör om det nyckeln finns i första eller andra halvan och fortsätt söka där (upprepa från punkt 1)
Om halvan du söker i krympt till ingenting: Avbryt. Det sökta elementet fanns inte med.

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_{2} n)$ $O\left(\log_2n\right)$ i värsta fallet. Varför det?

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 $\frac{n}{2}$ $\frac{n}{2}$ , andra varvet $\frac{n}{4}$ $\frac{n}{4}$ , tredje varvet $\frac{n}{8}$ $\frac{n}{8}$ . Vi är klara när det bara finns ett element kvar att titta på och då är $\frac{n}{2^{x}} = 1$ $\frac{n}{2^x}=1$ där $x$ $x$ är antal varv. Vi två-logaritmerar bägge led och får att $x = \log_{2} n$ $x=\log_2n$ .
Här följer en funktion för binärsökning:

def binary_search(the_list, key):
   low = 0
   high = len(the_list)-1
   found = False

   while low <= high and not found:
      middle = (low + high)//2
      if the_list[middle] == key:
         found = True
      else:
         if key < the_list[middle]:
            high = middle - 1
         else:
            low = middle + 1
   return found

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:

normalfallet, t ex att söka efter 14 i listan [9, 14, 23, 54, 92, 104]
att söka efter ett tal som inte finns med, t ex 15
att söka i en tom lista []
att söka efter vänstraste elementet 9 ...
... och högraste elementet 104.
att söka efter ett element bortom vänstra gränsen, t ex 8 ...
... och bortom högra gränsen, t ex 105.

Ett test består av ett hårdkodat testfall med ett förväntat resultat. När man utför testet jämför man testresultatet med det förväntade resultatet. Flera tester sätts upp i en matris där varje rad är ett test.

Det är skillnad på typer av variabler i python.

a = 1
b = 3.5
c = 'hej''

a + b # fungerar

a + c # fungerar inte. TypeError: unsupported operand type(s) for +: 'int' and 'str'

c + str(a) # fungerar, blir hej1

talstr = "123123"
talstr[0] + talstr[2] # blir strängn "13"
talstr[0:4] # från första till fjärde tecknet
a + int(talstr[0:4]) # 1232

Flera variabler som har med varandra att göra kan man sätta samman i en klass.

class Persondata:
   def __init__(self):
       self.name = ""
       self.age  = 0
       self.weight = 0
       self.length = 0

__init__ metoden är en specialmetod som konstruerar och initierar klassobjektet. self anger att det är en medlemsvariabel (ibland kallad fält eller atribut) som blir tilldelad ett värde.

a = Persondata()

a är ett objekt (eller en instans) av typen Persondata

Man kommer åt medlemsvariablerna med punktnotation

a.age = 73

Ofta vill man initiera samtidigt som man skapar objektet, det gör man genom att parametrisera __init__ metoden.

   def __init__(self, name, age, weight, length):
       self.name = name
       self.age = age
       self.weight = weight
       self.length = length

Förutsättningar

Testbeskrivning

Förväntat resultat

Har testet lyckats?

normalfall

lista [1, 3, 5, 7]
sokt 3

söker efter 3 i listan

I programmeringsspråket C måste programmeraren explicit skriva vilken typ en variabel ska ha.

int a = 3:

float f = 3.14;

char * s = "hej"

C-kompilatorn behöver informationen för att reservera plats i minnet för variablerna.

Klasser i C kallas structar.

struct Koordinat {
   int x;
   int y;
};

struct Koordinat p;
p.x = 1;
p.y = 2;

Man kan typdefiniera en ny typ med typedef