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

Ile wynosi duże O wyrażenia 3n² + 5n + 2?

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

Co oznacza f(n) = Θ(g(n))?

1. Af rośnie w tym samym tempie co g, ograniczona z góry i z dołu stałymi wielokrotnościami g
2. Bf jest zawsze mniejsza niż g dla każdego n, więc g ogranicza ją od góry, lecz nigdy od dołu
3. Cf rośnie ściśle szybciej niż g
4. Df rośnie ściśle wolniej niż g

Która z tych funkcji rośnie najwolniej, gdy n staje się duże?

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

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(k n log n)
3. CO(n log n + k log n)
4. DO(nk)

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

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

Programowanie dynamiczne jest przydatne, gdy problem ma:

1. ANakładające się podproblemy i optymalną podstrukturę
2. BŻadnych podproblemów, więc można go rozwiązać w jednym kroku
3. CWyłącznie losowe dane wejściowe
4. DPojedynczą pętlę

Które stwierdzenie dotyczące P i NP jest prawdziwe?

1. AKażdy problem z klasy P należy również do NP
2. BRozwiązań problemów NP nie da się szybko zweryfikować
3. CNP oznacza „niewielomianowy” (not polynomial)
4. DUdowodniono, że P ≠ NP

Jakie dwie rzeczy trzeba wykazać, aby udowodnić, że problem decyzyjny X jest NP-zupełny?

1. AX nie ma algorytmu wielomianowego, a X jest rozstrzygalny
2. BX redukuje się do problemu z P, a X należy do NP
3. CX należy do P, a X redukuje się do SAT
4. DX należy do NP, a znany problem NP-zupełny redukuje się do X w czasie wielomianowym