Algoritmeffektivitet – tidskomplexitet och rymdkomplexitet

Grundläggande datavetenskap

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Introduktion till Big-O-notation

Mäter hur tid och minne växer med indata
Exempel: $O(n)$, $O(n^2)$, $O(log\, n)$
'O' står för tillväxtens 'ordning', t.ex. O(n) = linjär

Tidskomplexitet – kontorsanalogi

Ett diagram som visar olika Big O-notationskomplexiteter

$O(1)$ - konstant tid - "Snabb blick" - "konstant"
$O(log\,n)$ - långsam ökning i tid - "Halvering av högar" - "logaritmisk"
$O(n)$ - linjär ökning - "Läsa dokument" - "linjär"
$O(n\,log\,n)$ - snabbare ökning i tid - "Sortera högar" - "linjäritmisk"
$O(n^2)$ - kvadratisk tidsökning - "Jämföra dokument" - "kvadratisk"

Rymdkomplexitet – kontorsanalogi

Ett diagram som visar olika Big O-notationskomplexiteter

$O(1)$ - konstant minne - "Skrivbordsyta" - "konstant"
$O(log\,n)$ - långsam ökning i minne - "Minimala anteckningar" - "logaritmisk"
$O(n)$ - linjär ökning - "Klisterlappar" - "linjär"
$O(n\,log\,n)$ - snabbare ökning i minne - "Tillfälliga högar" - "linjäritmisk"
$O(n^2)$ - kvadratisk minnesökning - "Jämförelserutnät" - "kvadratisk"

Nu kör vi en övning!

Grundläggande datavetenskap

Preparing Video For Download...