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

Jaka jest pesymistyczna złożoność czasowa sortowania przez wstawianie?

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

Jaka jest złożoność czasowa wyszukiwania liniowego w nieposortowanej tablicy n elementów (w najgorszym przypadku)?

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

Która klasa złożoności rośnie najszybciej dla dużych n?

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

Dlaczego w notacji dużego O zwykle pomija się podstawę logarytmu, jak w O(log n)?

1. AWszystkie logarytmy w informatyce mają podstawę 10, więc jest ona domyślna
2. BPodstawa ma znaczenie tylko dla małych n
3. CLogarytmy o różnych podstawach różnią się tylko stałym czynnikiem
4. DLogarytmy zawsze zaokrągla się do liczb całkowitych

Quicksort zawsze używa pierwszego elementu jako elementu osiowego. Dla jakich danych wykazuje zachowanie pesymistyczne?

1. ADla tablicy w losowej kolejności
2. BDla tablicy o długości 2
3. CDla tablicy już posortowanej
4. DDla tablicy, w której wszystkie elementy są różne

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)

Algorytm Strassena mnoży macierze, używając 7 zamiast 8 rekurencyjnych mnożeń bloków o połowie rozmiaru. Jaki jest jego czas działania?

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

Algorytm programowania dynamicznego Helda–Karpa rozwiązuje dokładnie problem komiwojażera. Jaki jest jego czas działania dla n miast?

1. AO(n³)
2. BO(n!)
3. CO(n² 2ⁿ)
4. DO(2^n²)