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 log n)
4. DO(n)

Problem zwykle nazywa się praktycznie rozwiązywalnym (tractable), jeśli:

1. ADa się go rozwiązać tylko przez sprawdzenie wszystkich możliwości
2. BDa się go rozwiązać w czasie wielomianowym
3. CDa się go rozwiązać w czasie stałym
4. DNie ma rozwiązania

Który z tych czasów działania jest wielomianowy?

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

Czy poprawne jest stwierdzenie, że algorytm O(n²) jest też O(n³)?

1. ATak, ale tylko gdy n jest mniejsze niż 100
2. BTak, bo duże O to ograniczenie górne, a n² nie rośnie szybciej niż n³
3. CNie, bo dla dużych n wartość n³ jest mniejsza niż n²
4. DNie, bo duże O musi zawsze podawać dokładne tempo wzrostu funkcji

Sortujesz raz tablicę n elementów, a potem odpowiadasz na k zapytań o przynależność za pomocą wyszukiwania binarnego. Jaki jest łączny koszt?

1. AO(n + k)
2. BO(nk)
3. CO(n log n + k log n)
4. DO(k n log n)

Przy monetach 1, 3 i 4 oraz kwocie 6, ile monet używa zachłanna metoda „najpierw największa moneta" w porównaniu z optimum?

1. AZachłanna używa 3 monet; optimum to 3
2. BZachłanna używa 2 monet; optimum to 2
3. CZachłanna używa 4 monet; optimum to 3
4. DZachłanna używa 3 monet; optimum to 2

Dlaczego wyszukiwanie binarne nie daje czasu O(log n) na liście jednokierunkowej?

1. ADotarcie do środkowego elementu wymaga O(n) kroków, bo nie ma bezpośredniego dostępu po indeksie
2. BList nie da się posortować
3. CPorównania na węzłach listy są wolniejsze
4. DWyszukiwanie binarne wymaga co najmniej dwa razy więcej pamięci

Co ustaliło twierdzenie Cooka–Levina?

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