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

Złożoność pamięciowa mierzy:

1. AMiejsce na dysku zajmowane przez plik programu po jego skompilowaniu
2. BIlość pamięci potrzebnej algorytmowi wraz ze wzrostem danych wejściowych
3. CFizyczny rozmiar komputera
4. DLiczbę linii kodu

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

1. Af jest zawsze mniejsza niż g dla każdego n, więc g ogranicza ją od góry, lecz nigdy od dołu
2. Bf rośnie ściśle szybciej niż g
3. Cf rośnie w tym samym tempie co g, ograniczona z góry i z dołu stałymi wielokrotnościami 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 log n)
2. BO(n)
3. CO(n²)
4. DO(log n)

Jak algorytm Prima buduje minimalne drzewo rozpinające?

1. ARozrasta jedno drzewo od wierzchołka startowego, dodając najtańszą krawędź wychodzącą z drzewa
2. BUsuwa najdroższą krawędź, dopóki nie znikną cykle
3. CUruchamia przeszukiwanie wszerz i zachowuje drzewo BFS
4. DSortuje wszystkie krawędzie według wagi i dodaje każdą, o ile nie utworzy cyklu w lesie

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

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

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

Mnożenie Karacuby spełnia T(n) = 3T(n/2) + O(n). Jakie jest rozwiązanie?

1. AΘ(n³)
2. BΘ(n log n)
3. CΘ(n²)
4. DΘ(n^{log₂ 3}), około n^1,585

Jak algorytm Bellmana–Forda wykrywa cykl o ujemnej wadze osiągalny ze źródła?

1. AZlicza cykle za pomocą przeszukiwania w głąb
2. BSprawdza, czy któraś krawędź ma ujemną wagę
3. CPo V − 1 rundach sprawdza, czy którąś krawędź można jeszcze zrelaksować
4. DUruchamia dwukrotnie algorytm Dijkstry i porównuje oba wyniki odległości