Algorytmy i struktury danych - Złożoność obliczeniowa
1. Kryteria porównywania algorytmów:
- prostota
- czytelność
- długość kodu
- poprawność
- czas realizacji
- zajętość pamięci
2. Złożoność obliczeniowa algorytmu – ilość zasobów komputerowych potrzebnych do jego wykonania.
Złożoność czasowa – to ilość czasu potrzebnego do wykonania zadania, wyrażona jako funkcja ilości danych.
Złożoność pamięciowa – to ilość pamięci potrzebnej do wykonania zadania, wyrażona jako funkcja ilości danych.
3. Rozmiar danych wejściowych to liczba elementów wejściowych lub całkowita liczba bitów reprezentująca tych danych.
4. Przykład algorytmu sortowania poprzez wstawianie:
5. Zbiór operacji dominujących danego algorytmu to zbiór takich operacji, których liczba jest proporcjonalna do liczby wszystkich operacji wykonanych przez cały algorytm. Operacją dominującą nie jest np. operacja wykonywana tylko jednokrotnie. Natomiast każda pętla lub odgałęzienie instrukcji warunkowej powinna zawierać operację dominującą.
6. Rozróżniamy następujące złożoności obliczeniowe:
- stała - Θ(1) - gdy czas wykonania algorytmu jest stały i niezależny od rozmiaru danych wejściowych,
- logarytmiczna - Θ(log n) - kiedy czas ten rośnie logarytmiczne wraz ze wzrostem wielkości danych. Logarytm jest niemal zawsze o podstawie 2 (w przypadku notacji asymptotycznych nie ma to aczkolwiek znaczenia, bowiem podstawa logarytmu może być zmieniona poprzez pomnożenie przez czynnik stały,
- liniowa - Θ(n) - czas działania jest proporcjonalny do rozmiaru danych wejściowych,
- liniowo-logarytmiczna - Θ(n log n) - złożoność jest iloczynem funkcji liniowej i logarytmicznej,
- kwadratowa - Θ(n^2) - liczba instrukcji algorytmu rośnie proporcjonalnie do kwadratu rozmiaru danych wejściowych,
- sześcienna - Θ(n^3) - liczba instrukcji algorytmu rośnie proporcjonalnie do sześcianu rozmiaru danych wejściowych,
- wielomianowa - Θ(n^r + n^r-1 + ... + n^1) - liczba instrukcji algorytmu rośnie proporcjonalnie do pewnego wielomianu rozmiaru danych wejściowych,
- wykładnicza - Θ(2^n) - czas wykonania rośnie wykładniczo względem rozmiaru danych,
- silni - Θ(n!) - czas wykonania rośnie z szybkością silni względem rozmiaru danych.
