Fiszki: Złożoność obliczeniowa prosto

Złożoność czasowa

Określa, jak czas wykonania algorytmu zmienia się w zależności od rozmiaru danych wejściowych.

Złożoność pamięciowa

Mówi o ilości pamięci potrzebnej do wykonania algorytmu w zależności od rozmiaru danych.

Klasy złożoności

Grupy problemów klasyfikowane według ich złożoności czasowej, np. $\displaystyle P$, $\displaystyle NP$, $\displaystyle NP$-trudne.

Algorytm

Zbiór kroków rozwiązujących problem. Może mieć różne złożoności w zależności od implementacji.

Notacja O wielkie

Sposób opisywania złożoności algorytmu, ignorując stałe i mniej istotne terminy, np. $\displaystyle O(n^2)$.

Złożoność liniowa

Oznaczana jako $\displaystyle O(n)$, wskazuje, że czas wykonania rośnie liniowo z rozmiarem danych.

Prawda czy fałsz: Złożoność $\displaystyle O(1)$ jest lepsza niż $\displaystyle O(n)$

Prawda, ponieważ złożoność stała nie zależy od rozmiaru danych.

Złożoność wykładnicza

Oznaczana jako $\displaystyle O(2^n)$, oznacza dramatyczny wzrost czasu wykonania przy zwiększeniu danych.

Przykład algorytmu sortującego

Sortowanie bąbelkowe ma złożoność $\displaystyle O(n^2)$, co czyni je wolnym dla dużych zbiorów danych.

Różnica między złożonością $\displaystyle O(n)$ a $\displaystyle O(n^2)$

$\displaystyle O(n)$ rośnie liniowo, podczas gdy $\displaystyle O(n^2)$ rośnie kwadratowo, co czyni je mniej efektywnym.

Uzupełnij zdanie: Złożoność algorytmu sortowania przez wstawianie to ___

$\displaystyle O(n^2)$ w najgorszym przypadku.

Problem NP

Klasa problemów, dla których rozwiązanie można zweryfikować w czasie wielomianowym, ale niekoniecznie znaleźć efektywnie.

Algorytmy rekurencyjne

Często mają złożoność wyższą niż ich iteracyjne odpowiedniki, np. $\displaystyle O(2^n)$ w przypadku rekurencji dla ciągu Fibonacciego.