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

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

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

Jaka jest złożoność czasowa przeszukiwania w głąb grafu zapisanego jako listy sąsiedztwa?

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

Jak nazywa się wzrost O(2ⁿ)?

1. ALogarytmiczny
2. BWykładniczy
3. CLiniowy
4. DWielomianowy

Jaka jest złożoność czasowa: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

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

Które stwierdzenie o wyborze k-tego najmniejszego elementu nieposortowanej tablicy jest poprawne?

1. AWybór zawsze wymaga Ω(n log n), bo wymaga sortowania
2. BQuickselect działa w O(log n) w najgorszym przypadku, bo schodzi rekurencyjnie tylko po jednej stronie piwota
3. CWybór jest możliwy tylko w O(n²)
4. DQuickselect działa w oczekiwanym czasie O(n), a mediana median gwarantuje O(n) w najgorszym przypadku

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

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