Podstawowe Pojęcia

1. Czasowa złożoność obliczeniowa: Określa, ile czasu potrzebuje algorytm na wykonanie swoich operacji w zależności od rozmiaru wejścia. Wyrażana jest za pomocą notacji O (wielkie O), która opisuje asymptotyczne zachowanie algorytmu.
2. Pamięciowa złożoność obliczeniowa: Mierzy ilość pamięci, jaką algorytm wymaga podczas działania. Podobnie jak czasowa złożoność, jest opisywana za pomocą notacji O  (wielkie O) .

Klasy Złożoności

1. P (czas wielomianowy): Klasa problemów, które mogą być rozwiązane przez algorytmy działające w czasie wielomianowym względem rozmiaru danych wejściowych.
2. NP (czas niedeterministyczny wielomianowy): Klasa problemów, dla których rozwiązanie może być zweryfikowane w czasie wielomianowym, ale niekoniecznie rozwiązane w takim czasie. Znalezienie rozwiązania tych problemów może być trudne, ale sprawdzenie poprawności rozwiązania jest łatwe.
3. NP-kompletne: Problemy, które są najtrudniejsze w klasie NP. Jeśli jakikolwiek problem NP-kompletny zostanie rozwiązany w czasie wielomianowym, wszystkie problemy NP mogą być tak rozwiązane.
4. NP-trudne: Problemy co najmniej tak trudne jak problemy NP-kompletne, ale niekoniecznie należące do klasy NP. Mogą być jeszcze trudniejsze do rozwiązania.

Przykłady Analizy Złożoności

1. Sortowanie bąbelkowe (Bubble Sort): Ma złożoność czasową O(n^2), co oznacza, że czas wykonania algorytmu rośnie kwadratowo wraz z rozmiarem danych wejściowych.
2. Sortowanie przez scalanie (Merge Sort): Ma złożoność czasową O(n log n), co czyni go bardziej efektywnym dla dużych zbiorów danych w porównaniu do sortowania bąbelkowego.

Znaczenie Złożoności Obliczeniowej

Podsumowanie