Efektivita algoritmů: časová a prostorová složitost

Koncepty v informatice

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Úvod do notace Big-O

Měří růst času a paměti v závislosti na velikosti vstupu
Příklady: $O(n)$, $O(n^2)$, $O(log\, n)$
„O" označuje „řád" růstu, např. O(n) = lineární

Časová složitost – analogie s kanceláří

Graf znázorňující různé složitosti v notaci Big O

$O(1)$ - konstantní čas - „Rychlý pohled" - „konstantní"
$O(log\,n)$ - pomalý růst času - „Dělení zásobníku" - „logaritmická"
$O(n)$ - lineární růst - „Čtení dokumentu" - „lineární"
$O(n\,log\,n)$ - rychlejší růst času - „Třídění hromady" - „lineárně logaritmická"
$O(n^2)$ - kvadratický růst času - „Porovnání dokumentů" - „kvadratická"

Prostorová složitost – analogie s kanceláří

Graf znázorňující různé složitosti v notaci Big O

$O(1)$ - konstantní prostor - „Plocha stolu" - „konstantní"
$O(log\,n)$ - pomalý růst prostoru - „Minimální poznámky" - „logaritmická"
$O(n)$ - lineární růst - „Samolepicí lístky" - „lineární"
$O(n\,log\,n)$ - rychlejší růst prostoru - „Dočasné hromady" - „lineárně logaritmická"
$O(n^2)$ - kvadratický růst prostoru - „Srovnávací mřížka" - „kvadratická"

Pojďme si procvičit!

Koncepty v informatice

Preparing Video For Download...