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

Co opisuje średni czas działania?

1. AOczekiwany czas przy danym rozkładzie danych wejściowych rozmiaru n
2. BCzas na najpopularniejszym komputerze
3. CWartość pośrodku między czasami działania w przypadku optymistycznym a pesymistycznym
4. DCzas dla danych o przeciętnej długości

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

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

Dostęp do elementu tablicy po indeksie zajmuje:

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

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

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

Który algorytm znajduje najkrótsze ścieżki z jednego źródła w grafie o nieujemnych wagach krawędzi?

1. AWe wszystkich przypadkach wymagany jest algorytm Bellmana–Forda
2. BAlgorytm Kruskala
3. CAlgorytm Dijkstry
4. DPrzeszukiwanie w głąb (DFS)

Quicksort zawsze używa pierwszego elementu jako elementu osiowego. Dla jakich danych wykazuje zachowanie pesymistyczne?

1. ADla tablicy, w której wszystkie elementy są różne
2. BDla tablicy o długości 2
3. CDla tablicy już posortowanej
4. DDla tablicy w losowej kolejności

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(2^n²)
3. CO(n² 2ⁿ)
4. DO(n³)

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

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