Algoritme-efficiëntie: tijd en ruimtecomplexiteit

Concepten in de informatica

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Introductie tot Big-O-notatie

  • Meet groei van tijd en geheugen bij grotere input
  • Voorbeelden: $O(n)$, $O(n^2)$, $O(log\, n)$
  • 'O' staat voor de orde van groei, bv. O(n) = lineair
Concepten in de informatica

Tijdcomplexiteit - met kantooranalogie

Een diagram met verschillende Big-O-complexiteiten

  • $O(1)$ - constante tijd - "Snelle blik" - "constant"
  • $O(log\,n)$ - langzame toename in tijd - "Stapels delen" - "logaritmisch"
  • $O(n)$ - lineaire toename - "Document lezen" - "lineair"
  • $O(n\,log\,n)$ - snellere toename in tijd - "Stapels sorteren" - "lineair-log"
  • $O(n^2)$ - kwadratische toename - "Documenten vergelijken" - "kwadratisch"
Concepten in de informatica

Ruimtecomplexiteit - met kantooranalogie

Een diagram met verschillende Big-O-complexiteiten

  • $O(1)$ - constante ruimte - "Bureauplek" - "constant"
  • $O(log\,n)$ - langzame toename in ruimte - "minimale notities" - "logaritmisch"
  • $O(n)$ - lineaire toename - "sticky notes" - "lineair"
  • $O(n\,log\,n)$ - snellere toename in ruimte - "tijdelijke stapels" - "lineair-log"
  • $O(n^2)$ - kwadratische toename - "vergelijkingsraster" - "kwadratisch"
Concepten in de informatica

Laten we oefenen!

Concepten in de informatica

Preparing Video For Download...