Wydajność algorytmów: złożoność czasowa i pamięciowa

Pojęcia informatyki

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Wprowadzenie do notacji Big-O

Mierzy wzrost czasu i pamięci wraz z rozmiarem danych
Przykłady: $O(n)$, $O(n^2)$, $O(log\, n)$
'O' oznacza 'rząd' wzrostu, np. O(n) = liniowy

Złożoność czasowa – analogia biurowa

Wykres przedstawiający różne złożoności w notacji Big O

$O(1)$ - czas stały - „Szybkie spojrzenie" - „stała"
$O(log\,n)$ - wolny wzrost czasu - „Podział stosu" - „logarytmiczna"
$O(n)$ - wzrost liniowy - „Czytanie dokumentu" - „liniowa"
$O(n\,log\,n)$ - szybszy wzrost czasu - „Sortowanie stosu" - „liniowo-logarytmiczna"
$O(n^2)$ - kwadratowy wzrost czasu - „Porównanie dokumentów" - „kwadratowa"

Złożoność pamięciowa – analogia biurowa

Wykres przedstawiający różne złożoności w notacji Big O

$O(1)$ - stała pamięć - „Przestrzeń biurka" - „stała"
$O(log\,n)$ - wolniejszy wzrost pamięci - „Minimalne notatki" - „logarytmiczna"
$O(n)$ - wzrost liniowy - „Karteczki" - „liniowa"
$O(n\,log\,n)$ - szybszy wzrost pamięci - „Tymczasowe stosy" - „liniowo-logarytmiczna"
$O(n^2)$ - kwadratowy wzrost pamięci - „Siatka porównań" - „kwadratowa"

Czas na ćwiczenia!

Pojęcia informatyki

Preparing Video For Download...