Algorytmy i złożoność: karta pracy z odpowiedziami

Jaką złożoność ma zwykle algorytm z dwiema zagnieżdżonymi pętlami, z których każda wykonuje się n razy?

1. AO(log n)
2. BO(n)
3. CO(2n)
4. DO(n²)

Który algorytm sortowania wielokrotnie zamienia miejscami sąsiednie elementy ustawione w złej kolejności?

1. ASortowanie bąbelkowe
2. BSortowanie przez scalanie
3. CSortowanie przez kopcowanie
4. DSortowanie szybkie (quicksort)

Czego wyszukiwanie binarne wymaga od danych wejściowych?

1. ADługość tablicy musi być potęgą dwójki
2. BTablica może zawierać tylko liczby dodatnie
3. CTablica musi być posortowana
4. DTablica może mieć najwyżej 1000 elementów

Jaka jest złożoność czasowa obliczania n-tej liczby Fibonacciego za pomocą tablicy wypełnianej wstępująco (bottom-up)?

1. AO(2ⁿ)
2. BO(log n)
3. CO(n)
4. DO(n²)

Jaka jest złożoność czasowa algorytmu Bellmana–Forda dla grafu o V wierzchołkach i E krawędziach?

1. AO(V + E)
2. BO(E log V)
3. CO(V³ × E)
4. DO(V × E)

Dlaczego wiele bibliotecznych procedur sortowania przełącza się na sortowanie przez wstawianie dla bardzo małych podtablic?

1. ASortowanie przez wstawianie ma mały narzut i jest szybkie dla małych lub prawie posortowanych danych
2. BSortowanie przez wstawianie jest O(n log n) w najgorszym przypadku
3. CSortowanie przez wstawianie zużywa mniej pamięci niż każdy inny algorytm sortowania dla dużych danych
4. DAlgorytmy rekurencyjne nie radzą sobie z tablicami poniżej 10 elementów

Problem stopu pokazuje, że:

1. AŻaden algorytm nie może rozstrzygnąć dla każdego programu i danych wejściowych, czy program się zatrzyma
2. BKażdy program w końcu się zatrzymuje
3. CNiektóre programy działają szybciej na szybszych komputerach, więc zatrzymanie zależy od sprzętu
4. DNależy unikać pętli

Mnożenie Karacuby spełnia T(n) = 3T(n/2) + O(n). Jakie jest rozwiązanie?

1. AΘ(n log n)
2. BΘ(n³)
3. CΘ(n^{log₂ 3}), około n^1,585
4. DΘ(n²)