Algorytmika i złożoność

Question 1

Jaka jest złożoność czasowa sortowania szybkiego (QuickSort) w przypadku pesymistycznym?

Accepted Answer

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.

Question 2

Który algorytm ma złożoność O(n log n) w przypadku optymistycznym, średnim ORAZ pesymistycznym, ale wymaga dodatkowej pamięci rzędu O(n)?

Accepted Answer

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.

Question 3

Tablica [7, 3, 9, 1, 5] jest sortowana rosnąco metodą bąbelkową, z porównywaniem sąsiednich par od lewej strony. Jak wygląda tablica po pierwszym PEŁNYM przebiegu?

Accepted Answer

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.

Question 4

Ile porównań wykona w najgorszym przypadku wyszukiwanie binarne w posortowanej tablicy liczącej 4096 elementów?

Accepted Answer

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.

Question 5

Jaki warunek MUSI być spełniony, aby w zbiorze danych można było zastosować wyszukiwanie binarne?

Accepted Answer

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.

Question 6

Programista tworzy bufor wydruku, w którym dokumenty mają być drukowane dokładnie w kolejności ich zgłoszenia. Którą strukturę danych powinien wybrać i dlaczego?

Accepted Answer

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.

Question 7

Który blok schematu blokowego jako JEDYNY posiada dwa wyjścia?

Accepted Answer

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.

Question 8

Prześledź pseudokod: x = 200; k = 0; dopóki x > 1 wykonuj: x = x div 2; k = k + 1; koniec dopóki; pisz k. Jaką wartość wypisze algorytm?

Accepted Answer

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).

Question 9

Ile wynosi NWD(84, 36) wyznaczone algorytmem Euklidesa w wersji z resztą z dzielenia?

Accepted Answer

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.

Question 10

Co stanie się podczas uruchomienia funkcji rekurencyjnej, w której pominięto warunek zakończenia (przypadek bazowy)?

Accepted Answer

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.

To nie koniec powtórki