Algorytmika i złożoność

Dlaczego: Skrajnie źle dobrany element osiowy (na przykład zawsze pierwszy element w tablicy już posortowanej) dzieli zakres na część pustą i (n-1)-elementową, więc poziomów rekurencji jest n zamiast log n, a na każdym wykonuje się porównania liniowe. Odpowiedź O(n log n) kusi, bo to złożoność optymistyczna i średnia tego algorytmu, podawana zwykle jako jego wizytówka.

Dlaczego: Podział jest tu zawsze na dwie równe połowy niezależnie od zawartości danych, więc poziomów zawsze jest log n, a scalanie każdego poziomu kosztuje n operacji — stąd gwarancja we wszystkich trzech przypadkach. Ceną jest tablica pomocnicza o rozmiarze n. QuickSort kusi jako druga metoda dziel i zwyciężaj, ale jego podział zależy od pivota i degeneruje się do kwadratowej.

Dlaczego: Przebieg to cztery porównania par: (7,3) zamiana, (7,9) bez zmian, (9,1) zamiana, (9,5) zamiana — największa wartość wypływa na koniec, reszta przesuwa się tylko o jedną pozycję. Najczęstszy błąd to zatrzymanie się po pierwszej zamianie albo podanie tablicy w pełni posortowanej: jeden przebieg ustawia na swoim miejscu wyłącznie jeden element.

Dlaczego: Każdy krok odrzuca połowę zakresu, więc liczba kroków to logarytm o podstawie 2 z liczby elementów: 2 do potęgi 12 daje 4096, czyli po dwunastu połowieniach zostaje jeden element. Wartość 2048 kusi, bo zakłada jednorazowe podzielenie zbioru na pół, a 4096 to liczba porównań wyszukiwania liniowego, nie binarnego.

Dlaczego: Algorytm porównuje szukaną wartość z elementem środkowym i na tej podstawie odrzuca całą jedną połowę zakresu — taki wniosek jest prawdziwy tylko wtedy, gdy wartości rosną lub maleją monotonicznie. Na zbiorze nieuporządkowanym metoda nie działa wolniej, tylko błędnie: odrzuca połowę, w której leży szukany element, i zwraca informację o jego braku.

Dlaczego: FIFO oznacza dodawanie na końcu (enqueue) i pobieranie z początku (dequeue), więc kolejność obsługi jest identyczna z kolejnością zgłoszeń. Stos kusi, bo również daje operacje w czasie stałym, ale odkłada i zdejmuje z tego samego końca, przez co wydrukowałby dokumenty w odwrotnej kolejności. Drzewo BST porządkuje po wartości klucza, a nie po czasie zgłoszenia.

Dlaczego: Ten blok zawiera pytanie o wartość logiczną i rozgałęzia sterowanie na drogę TAK i drogę NIE — to jedyne miejsce, w którym przebieg algorytmu się rozdziela. Prostokąt (przypisanie, obliczenie) i równoległobok (czytaj, pisz) mają zawsze dokładnie jedno wyjście, owal START jedno, a owal STOP nie ma żadnego. Rysowanie dwóch strzałek z prostokąta to klasyczny błąd.

Dlaczego: Kolejne wartości x przy dzieleniu całkowitym to 100, 50, 25, 12, 6, 3, 1 — siedem obiegów, po których warunek x > 1 przestaje być prawdziwy. Pułapką jest krok 25 div 2, gdzie wynikiem jest 12, a nie 12,5. Ta pętla to wzorzec złożoności logarytmicznej: dzielenie zmiennej przez 2 w każdym obiegu daje O(log n).

Dlaczego: W każdym obiegu liczy się r = a mod b, po czym a przyjmuje wartość b, a b wartość r: 84 mod 36 daje 12, potem 36 mod 12 daje 0. Pętla kończy się, gdy b osiągnie zero, a wynikiem jest ostatnia niezerowa wartość a. Odpowiedź 252 kusi, bo to NWW tej pary (iloczyn liczb podzielony przez NWD), a 6 to wspólny dzielnik, ale nie największy.

Dlaczego: Każde wejście do funkcji rezerwuje na stosie ramkę z parametrami i adresem powrotu, a bez przypadku bazowego nic nie przerywa łańcucha wywołań, więc pamięć stosu się wyczerpuje. Odpowiedź o błędzie kompilacji kusi, ale składnia takiego kodu jest poprawna — usterka ujawnia się dopiero w czasie wykonania. Brak warunku zakończenia łamie cechę skończoności, więc taki zapis nie jest algorytmem.