Zadania ze złożoności obliczeniowej

Zadanie 1.

Napisz program, który dla podanej liczby n wypisze jej rozkład na czynniki pierwsze. Oblicz asymptotyczną złożoność optymistyczną i pesymistyczną.

Zadanie 2.

Dana jest tablica a, która zawiera parami różne liczy całkowite. W tej tablicy chcemy znaleźć drugą co do wielkości liczbę przy użyciu możliwie małej liczby porównań. Standardowe podejście dałoby około 2n operacji porównania dwóch liczb, jednak okazuje się, że można to nieco poprawić. Opis algorytmu poniżej.

Najpierw szukamy maksimum w tablicy, w dosyć specyficzny sposób:

• Porównaj a[0] z a[1], a[2] z a[3], a[4] z a[5] itd.
• Każde takie porównanie pozwala nam odrzucić jedną liczbę, bo na pewno nie będzie ona największa w całej tablicy. Ostatecznie wyrzucimy około połowę (w tablicy nieparzystego rozmiaru "mniejszą połowę") wszystkich liczb.
• Jeśli została jedna liczba, to znaleźliśmy maksimum. Jeśli nie - trzeba wykonać się rekurencyjnie dla liczb, które pozostały.

W ten sposób znajdziemy maksimum, nazwijmy je M. Teraz załóżmy, że zapisaliśmy sobie gdzieś na boku listę wszystkich par liczb, które porównywaliśmy, tj. mamy listę wpisów "porównuję x z y". Łatwo zauważyć, że na pewno kiedyś musieliśmy porównać M z drugą co do wielkości liczbą w tablicy. Wystarczy więc spojrzeć na wszystkie liczby, które były kiedyś porównane z M i znaleźć największą spośród nich (to już robimy normalnie).

Zadanie polega na możliwie dokładnym policzeniu liczby wykonanych porównań. Nie jest ważny czas działania całości algorytmu (który przy dobrej implementacji wynosi O(n)). Można ograniczyć się do przypadku, gdy n jest potęgą dwójki.

Zadanie 3.

Rozwiąż równanie rekurencyjne T(n) = n + 2 T(2/3 n).