Symulacja przedstawia złożoności obliczeniowe różnych rozwiązań tego samego problemu obliczeniowego – znalezienia NWD dwóch liczb. Dane są dwie liczby – $a$ oraz $b$, takie że $a > b$. Naszym zadaniem jest znalezienie ich największego wspólnego dzielnika. By to zrobić, możemy wykorzystać kilka metod.

• Rozwiązanie siłowe (ang. brute force) – to metoda polegająca na sprawdzeniu wszystkich możliwych przypadków w celu znalezienia rozwiązania danego problemu, w tym wypadku sprawdzamy wszystkie liczby całkowite od 1 do $b$, poszukując tych, które są wspólnymi dzielnikami liczb $a$ oraz $b$ – złożoność tego rozwiązania to $O(min(a, b))$.

• Algorytm Euklidesa z wykorzystaniem iteracji – jego złożoność obliczeniowa wynosi $O(log(min(a, b)))$. Więcej na temat tego algorytmu znajdziesz w e‑materiale Algorytm EuklidesaP7OAFYVSiAlgorytm Euklidesa.

• Algorytm Euklidesa z użyciem rekurencji – jego złożoność obliczeniowa wynosi również $O(log(min(a, b)))$. Więcej na temat tego algorytmu znajdziesz w e‑materiale Algorytm EuklidesaP7OAFYVSiAlgorytm Euklidesa.

• Rozkład na czynniki pierwsze – jego złożoność obliczeniowa to $O\left(\sqrt{\min a,\ b}\right)$.

• Algorytm Steina – jego złożoność obliczeniowa to $O(log(a) * log(b))$.

Przeanalizuj wykres interaktywny. Przyjrzyj się temu, jak zmienia się liczba wykonywanych operacji dla poniższych par liczb:

• przypadek 1: 27 oraz 5,

• przypadek 2: 20 oraz 23,

• przypadek 3: 15 oraz 12,

• przypadek 4: 94 oraz 87.

Przygotuj własną symulację, w której zapiszesz złożoność obliczeniową dla różnych rozwiązań tego samego problemu, np. sortowania zbioru liczb. Złożoność oblicz dla różnych przypadków.