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

Czym jest memoizacja?

1. APisaniem komentarzy obok każdego wiersza kodu
2. BAutomatyczną zamianą rekurencji na równoważną pętlę, tak że stos wywołań nie jest potrzebny
3. CZapamiętywaniem wyników wywołań funkcji, tak by powtórne wywołania były obsługiwane z pamięci
4. DZwalnianiem pamięci po powrocie z funkcji

Jaka jest złożoność czasowa znalezienia największej wartości w nieposortowanej tablicy n liczb?

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

Czym jest algorytm siłowy (brute force)?

1. AAlgorytmem, który zawsze używa rekurencji
2. BAlgorytmem, który losowo zgaduje odpowiedź
3. CAlgorytmem, który sprawdza wszystkie możliwe rozwiązania kandydujące
4. DAlgorytmem działającym na wielu procesorach

Jaka jest złożoność czasowa mnożenia dwóch macierzy n × n standardową potrójną pętlą?

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

Co oblicza algorytm Floyda–Warshalla i jak szybko?

1. ANajkrótsze ścieżki między wszystkimi parami wierzchołków w O(V³)
2. BMinimalne drzewo rozpinające w O(E log V)
3. CNajkrótsze ścieżki z jednego wierzchołka źródłowego do wszystkich pozostałych w O(V + E)
4. DPorządek topologiczny w O(V²)

Jaka jest złożoność czasowa: for i = 1 to n: for j = 1 to i: wykonaj pracę O(1)?

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

Co by wynikało, gdyby ktoś znalazł algorytm wielomianowy dla jednego problemu NP-zupełnego?

1. AProblem stopu stałby się rozstrzygalny
2. BWszystkie algorytmy o czasie wykładniczym od razu działałyby w czasie liniowym
3. CKażdy problem z NP dałoby się rozwiązać w czasie wielomianowym, więc P = NP
4. DTylko ten jeden problem przeszedłby do P

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²)