Analiza algorytmów

WPROWADZENIE

https://en.wikipedia.org/wiki/Computational_complexity

Analiza algorytmów jest dziedziną informatyki zajmującą się badaniem algorytmów.

Kryteria analizy algorytmów.

• Poprawność - daje dobry wynik dla każdej możliwej konfiguracji danych wejściowych [debugging, dowody formalne].
• Złożoność obliczeniowa czasowa i pamięciowa.
• Optymalność - interesuje nas algorytm najlepszy pod względem złożoności obliczeniowej.
• Efektywność - użyteczność w praktycznych sytuacjach.

Złożoność obliczeniowa algorytmu (ang. computational complexity).

• Rozmiar zadania (złożoność pamięciowa) - rozmiar danych wejściowych, roboczych, wyjściowych.
• Czas działania algorytmu (złożoność czasowa) - liczba kroków przekładająca się na czas pracy maszyny realizującej algorytm.

Przy badaniu złożoności czasowej często wystarcza zbadanie tzw. operacji dominujących, a nie dokładnie wszystkich operacji. Najbardziej czasochłonne operacje to zwykle instrukcja porównania (if) i instrukcja przypisania. Oznaczamy: Tc - czas wykonania jednej instrukcji porównania (compare), Ta - czas wykonania jednej instrukcji przypisania (assign). Złożoność obliczeniową charakteryzujemy przy pomocy tzw. notacji O.

Przy badaniu złożoności czasem spotykamy sytuację, że złożoność zależy od konfiguracji danych początkowych. Wtedy można przeprowadzić m.in. trzy analizy, dla przypadku najgorszego, średniego i najkorzystniejszego. Korzysta się przy tym zwykle z analizy statystycznej.

W badaniach algorymów czasem wykonuje się analizę empiryczną. Musimy wtedy dysponować poprawną i pełną implementacją algorytmu. Ponadto musimy wybrać zestaw danych wejściowych. Na ogół mamy trzy możliwości: użyć danych rzeczywistych, losowych lub złośliwych (przypadek pesymistyczny).

ZAPIS Z DUŻYM "O"

Zapis z dużym "O" podaje asymptotyczne ograniczenie górne funkcji.

O(g(n)) = {f(n): istnieją dodatnie stałe c i n_0, takie że 0 <= f(n) <= c g(n) dla wszystkich n >= n_0}.

Podstawowe klasy złożoności algorytmów (od najniższej do najwyższej).

• stała O(1),
• logarytmiczna O(log n),
• liniowa O(n),
• liniowo-logarytmiczna O(n log n),
• kwadratowa O(n^2),
• sześcienna O(n^3),
• wykładnicza O(a^n).

FUNKCJA SILNIA

Zbadamy złożoność czasową algorytmu rekurencyjnego obliczającego funkcję silnia. Zakładamy, że najbardziej czasochłonną operacją jest instrukcja porównania if.

def silnia(n):                # wg Wróblewskiego
    """Funkcja silnia w wersji rekurencyjnej."""
    if n == 0:
        return 1
    else:
        return n * silnia(n-1)

T(0) = Tc,
T(n) = Tc + T(n-1)   dla n >= 1

T(n) = Tc + Tc + T(n-2) = 2*Tc + T(n-2),
T(n) = n*Tc + T(0) = (n+1)*Tc.          # złożoność praktyczna
Złożoność klasy O(n).                   # złożoność teoretyczna

def silnia(n):
    """Funkcja silnia w wersji iteracyjnej."""
    result = 1                      # Ta
    while n > 1:                    # Tc
        result = result * n     # Ta
        n = n - 1               # Ta
    return result

T(1) = Ta + Tc,
T(n) = Ta + Tc + (n-1)*(Tc + 2*Ta),
T(n) = Ta*(2*n - 1) + Tc*(n) dla n > 1.
Złożoność klasy O(n).

ZŁOŻONOŚĆ OBLICZENIOWA

Złożoność obliczeniową należy opisywać biorąc pod uwagę liczbę bitów danych B dostarczonych na wejście. Takie podejście pomaga ustrzec się od błędów. Czasem można łatwo przejść w opisie od bitów B do innego, wygodniejszego parametru.

Przykład: Sprawdzić, czy liczba całkowita N jest liczbą pierwszą. Metoda sprawdzenia polega na dzieleniu liczby N kolejno przez liczby 2, 3, 4, ..., |_sqrt(N)_|.

Pierwsza analiza złożoności: Mierzymy złożoność jako liczbę dzieleń liczba przez liczbę, co daje O(sqrt(N)) jednostek pracy.

Druga analiza złożoności: Do przedstawienia liczby N potrzebujemy B bitów, N = 2^B. W tej sytuacji złożoność wyrażona przez liczbę bitów wynosi O(sqrt(2^B)) = O(2^(B/2)) = O(1.4142^B). Złożoność obliczeniowa jest wykładnicza, czyli algorytm jest powolny.

PROBLEMY ŁATWE I TRUDNE

Problemy łatwe mają znane metody szybkiego ich rozwiązywania (w czasie wielomianowym).

Problem jest trudny, jeżeli udowodnimy, że nie istnieje szybka metoda jego rozwiązania. Nie wystarczy wskazać jakiś szczególny powolny algorytm do jego rozwiązywania [H. S. Wilf, Algorithms and Complexity, Internet Edition 1994, https://www.math.upenn.edu/~wilf/].

Warto pamiętać, że trudne problemy mogą mieć łatwe instancje, czyli szczególne przypadki, w których łatwo można znaleźć rozwiązanie [np. kolorowanie wierzchołków grafu cyklicznego].