Gå till innehållet

DD2350 Algoritmer, datastrukturer och komplexitet 9,5 hp

Tillfälleskod Termin(er) Period(er) Föreläsare
50381 HT2025 1-2 Viggo Kann, Per Austrin

Anteckningar med utgångspunkt i föreläsningsslides.

Föreläsning 1

I schemat: den 25 augusti 2025

Algoritm: En ändlig, stegvis beskrivning av hur ett problem kan lösas. Oftast består detta i att, med hjälp av indata som beskriver probleminstansen, producera utdata som beskriver dess lösning.

En algoritm kan sägas beräkna en funktion \(A:\{\text{Probleminstanser}\}\mapsto\{\text{Lösningar}\}\).

Analys av algoritmer

Tidskomplexitet: Hur körtiden beror av probleminstansens storlek.

\[T_A(n)="\text{körtiden för }A\text{ på probleminstanser av stl. }n"\]

Det finns tre typer:

  1. Värsta-fallskomplexitet: Överskrids aldrig. Grundad i utvecklad matematisk teori.
  2. Medelfalls-komplexitet: Ger realistisk bild -- men ofta oklart vad som är "realistiskt" (+ lätt att förbise risk för överbelastning).
  3. Bästa-fallskomplexitet: Sällan intressant.

Asymptotisk analys: Studera \(T(n)\) när \(n\to\infty\).

Ordo-notation: \(\mathcal{O}(f(n))\) är alla funktioner som växer högst lika snabbt som \(f(n)\).

Notation Tillväxthastighet
\(\omega(f(n))\) Snabbare än \(f(n)\)
\(\Omega(f(n))\) Minst lika snabbt som \(f(n)\)
\(\Theta(f(n))\) Lika snabbt som \(f(n)\), dvs. "proportionerligt".
\(\mathcal{O}(f(n))\) Högst lika snabbt som \(f(n)\)
\(o(f(n))\) Långsammare än \(f(n)\)

RAM-modellen

RAM = "Random Access Machine"

Väsentligen en slags assembler-språk, med en uppsättnings instruktioner för att kopiera data mellan register och minne samt utföra enkla operationer. Liknar hur en riktig dator fungerar.

Ett program består i denna modell av vanliga satser som utförs sekventiellt (i betydelsen inte parallellt) och som endast kan läsa/skriva ett konstant antal minnesplatser. Varje sats tar konstant tid (konstant antal klockcykler -- men kan vara olika för olika instruktioner)!

Kostnadsmått

Två olika kostnadsmått:

  • Enhetskostnad: Varje operation tar en tidsenhet. Varje variabel tar en minnesenhet. Beräkningsmodell: RAM.
  • Bitkostnad: Varje bitoperation tar en tidsenhet. Varje bit eller maskinord tar en minnesenhet. Beräkningsmodell: Word-RAM-modellen. Används när algoritmen räknar med tal av godtycklig storlek.

Exempel: Addition av två \(n\)-bitarsheltal. Med enhetskostnad är tidskomplexiteten \(\mathcal{O}(1)\); med bitkostnad är den \(\mathcal{O}(n)\).

Minneskomplexitet

Anges oftast med \(\mathcal O\)-notation.

Exempel: for i from 1 to n do print(i)

Indata Utdata Arbetsminne
Enhetskostnad Storlek 1 Storlek \(n\) 1 cell (variabeln i)
Bitkostnad Storlek \(\log n\) Storlek \(n\log n\) \(\log n\) bitar

Föreläsning 2

Sortering

Två klasser av algoritmer:

  • Jämförelsebaserad: det enda vi kan göra är parvisa jämförelser av objekt
  • Dataspecifik: använder även specifika egenskaper hos typen av objekt som sorteras

Urvalssortering

  • Hitta index \(i\) för minsta elementet
  • Byt plats på första elementet och index \(i\)
  • Upprepa för listans svans

Tidskomplexitet \(\Theta(n^2)\)?

Mergesort

  • Dela upp listan i \(n\) sublistor.
  • Sammanfoga sublistorna upprepade gånger tills endast en sublista återstår. Denna kommer att vara sorterad.

Minnesåtgång: \(\mathcal O(n)\)

Hur analysera tidskomplexitet:

Låt \(T(n)="\text{tidsåtgång för sortering av }n\text{ tal med mergesort}"\)

Rekurrens: \(T(n)=\begin{cases}\Theta(1)&\text{om }n=1\\T(\left\lfloor\frac n2\right\rfloor)\end{cases}\)

Mästarsatsen

Ger en generell lösning till rekurrenser såsom den i mergesort.

Antag \(T(1)=\Theta(1)\) och \(T(n)=a\cdot T(\frac nb)+\Theta(f(n))\) Låt \(c=\frac{\log a}{\log b}\).

\(T(n)=\begin{cases}\Theta(f(n))&\text{om }f(n)=\Omega(n^{c'})\text{ för konstant }c'\gt c\\\Theta(n^c)&\text{om }f(n)=O(n^{c'})\text{ för konstant }c'\lt c\\\Theta(n^c\log n)&\text{om }f(n)=\Theta(n^c)\end{cases}\)

Quicksort

  1. Välj ett pivot-element \(x\) på något sätt
  2. Partitionera \(A\) efter \(x\), dvs. ordna om \(A\) s.a.
    • Alla element som är \(\leq x\) kommer t.v.
    • Alla element som är \(\gt x\) kommer t.h.
  3. Anropa Quicksort rekursivt på delarna vänster respektive höger om \(x\).

I medelfallet spelar valet av \(x\) ingen roll.

Värsta fallet \(\Omega(n^2)\). Hur kan detta undvikas?

  • Hitta medinanen (kan göras i \(O(n)\), värsta fall \(\mathcal O(n\log n)\)). Detta är dock långsammare än mergesort i praktiken.
  • Välj ett slumpmässigt element i arrayen -- i värsta fall \(O(n\log n)\) men bara med hög sannolikhet
  • Introspective sort: Byt algoritm om rekursionen blir för djup.

Basfall för rekursiva algoritmer

  1. När vi bara har ett element kvar -- naturligt men ofta långsamt i praktiken (många små rekursiva anrop)
  2. Byt till t.ex. insättningssortering när antalet element är relativt litet.

Abstrakta datatyper (ADT)

En slags specifikation av vilka operationer som ska stödjas och hur de skall bete sig. Ger dock ingen information om hur detta skall implementeras.

Exempel: En stack är en datastruktur med operationerna push(x) och pop().

En datastruktur är en specifik implementation av en ADT. T.ex. en stack kan implementeras som t.ex. en dynamisk array, länkad lista, etc.

Prioritetsköer

En kö där varje objekt har en prioritet. Operationer: insert, remove och ibland även changeKey (ändra prioritet för ett objekt).

Kan användas för sortering (heap sort).

Heap

En heap är ett komplett binärt träd som uppfyller heapegenskapen.

  • Komplett binärt träd: alla nivåer i trädet är fyllda utom den sista. Sista nivån fylls på från vänster.
  • Heapegenskapen: varje nod är mindre än (eller lika stor som) sin förälder.

Insert:

  1. Lägg till "sist" i heapen.
  2. Så länge objektet är större än sin förälder: byt plats.
  3. Tidskomplexitet: \(\mathcal O(\log n)\)

Remove:

  1. Ta bort roten och flytta upp sista elementet.
  2. Så länge objektet är mindre än sitt största barn: byt plats.
  3. Tidskomplexitet: \(\mathcal O(\log n)\)

Ordlista / associativ array

..................