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

Jaka jest optymistyczna złożoność czasowa sortowania przez wstawianie dla już posortowanej tablicy?

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

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

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

Czym jest przypadek bazowy funkcji rekurencyjnej?

1. APierwszym wierszem funkcji
2. BPrzypadkiem, na który odpowiada się bezpośrednio, bez kolejnego wywołania rekurencyjnego
3. CWywołaniem zużywającym najwięcej pamięci
4. DPrzypadkiem z największymi danymi wejściowymi, który obsługuje się przed jakimikolwiek wywołaniami rekurencyjnymi

Jakie jest rozwiązanie rekurencji T(n) = T(n − 1) + O(n)?

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

Jaka jest pesymistyczna złożoność czasowa sortowania szybkiego (quicksort)?

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

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

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

Dyskretny problem plecakowy (0/1) rozwiązany programowaniem dynamicznym zajmuje czas O(nW). Dlaczego nazywa się to złożonością pseudowielomianową?

1. APonieważ n jest zawsze małe
2. BPonieważ algorytm jest randomizowany, a jego czas działania zmienia się przy każdych danych
3. CW jest liczbą, więc czas jest wykładniczy względem liczby bitów użytych do zapisania W
4. DPonieważ działa tylko dla W = 0

Co ustaliło twierdzenie Cooka–Levina?

1. AKażdy problem NP można rozwiązać w czasie wykładniczym
2. BP nie jest równe NP
3. CProblem spełnialności formuł logicznych (SAT) jest NP-zupełny
4. DProblem stopu jest nierozstrzygalny