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

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

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

Co oznacza, że operacja działa w czasie O(1)?

1. APrzetwarza dokładnie jeden element na sekundę czasu działania
2. BMożna ją wykonać tylko raz
3. CZawsze trwa dokładnie jedną sekundę
4. DJej czas działania nie rośnie wraz z rozmiarem danych wejściowych

Czas działania algorytmu wynosi O(n). Jak nazywa się ten wzrost?

1. AStały
2. BLogarytmiczny
3. CLiniowy
4. DKwadratowy

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

Ile mniej więcej porównań potrzebuje wyszukiwanie binarne w najgorszym przypadku w posortowanej tablicy 1,000,000 elementów?

1. AOkoło 100
2. BOkoło 1,000
3. COkoło 500,000
4. DOkoło 20

Jaki jest czas działania sortowania pozycyjnego LSD (radix sort) dla n liczb całkowitych o d cyfrach w systemie o podstawie k?

1. AO(n log n)
2. BO(dn log k)
3. CO(d(n + k))
4. DO(n²)

Co trzeba zrobić, aby wykazać, że nowy problem X jest NP-trudny?

1. AWykazać, że X można zweryfikować w czasie wielomianowym
2. BWykazać, że X nie ma algorytmu wielomianowego dla małych danych
3. CZredukować znany problem NP-trudny do X w czasie wielomianowym
4. DZredukować X do znanego problemu NP-trudnego w czasie wielomianowym

Korzystając z twierdzenia o rekurencji uniwersalnej (master theorem), rozwiązaniem T(n) = 8T(n/2) + O(n²) jest:

1. AΘ(n³)
2. BΘ(n²)
3. CΘ(n log n)
4. DΘ(n² log n)