Föreläsningar

Föreläsning 2

Hur man analyserar algoritmer

[kapitel 3]
OH-bilder från denna föreläsning

Hur kan man mäta algoritmers effektivitet?

Provkörning eller analys.

Vad menas med pseudokod och vad kan man ha den till?

Hur kan man bevisa att en algoritm är korrekt?

Existensbevis, induktionsbevis, motsägelser.

Men körtiden beror ju på en massa olika saker...

Komplexitetsmått, medelfall och värsta fall.

Hur beskriver man algoritmers effektivitet?

Asymptotiska mått.
O-notationen.
Olika klasser av effektivitet.