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

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

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

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

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

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

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

Jaka jest złożoność czasowa algorytmu Bellmana–Forda dla grafu o V wierzchołkach i E krawędziach?

1. AO(V + E)
2. BO(V × E)
3. CO(V³ × E)
4. DO(E log V)

Który algorytm sortowania jest stabilny?

1. ASortowanie przez scalanie
2. BSortowanie przez kopcowanie
3. CSortowanie przez wybieranie (typowa wersja)
4. DSortowanie szybkie (typowa wersja w miejscu)

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

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

Który algorytm znajduje minimalne drzewo rozpinające, wielokrotnie dodając najtańszą krawędź, która nie tworzy cyklu?

1. AAlgorytm Dijkstry
2. BAlgorytm Kruskala
3. CAlgorytm Prima startujący z jednego wierzchołka
4. DAlgorytm Floyda–Warshalla

Najkrótsze ścieżki proste można znaleźć w czasie wielomianowym. Co wiadomo o znajdowaniu najdłuższej ścieżki prostej między dwoma wierzchołkami w ogólnym grafie?

1. AMożna je rozwiązać algorytmem Dijkstry z wagami o przeciwnym znaku
2. BZawsze jest rozwiązywalne w O(V + E)
3. CJest nierozstrzygalne
4. DJest NP-trudne