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

Co opisuje średni czas działania?

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

Jak nazywa się wzrost O(2ⁿ)?

1. AWielomianowy
2. BLiniowy
3. CLogarytmiczny
4. DWykładniczy

Jaka jest złożoność czasowa wyszukiwania liniowego w nieposortowanej tablicy n elementów (w najgorszym przypadku)?

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

Przeszukiwanie wszerz w grafie nieważonym znajduje:

1. APorządek topologiczny w dowolnym grafie
2. BNajkrótsze ścieżki w grafach zawierających ujemne wagi krawędzi
3. CMinimalne drzewo rozpinające
4. DNajkrótsze ścieżki (w liczbie krawędzi) od wierzchołka startowego

Dlaczego programowanie dynamiczne nie daje realnego przyspieszenia sortowania przez scalanie?

1. ASortowanie przez scalanie już jest O(n)
2. BSortowanie przez scalanie nie ma struktury rekurencyjnej
3. CProgramowanie dynamiczne działa tylko na problemach grafowych, a nie na tablicach
4. DJego podproblemy się nie nakładają, więc nie ma czego ponownie wykorzystać

Funkcja wykonuje jedną pętlę n iteracji, a potem osobno drugą pętlę n iteracji. Jaka jest jej złożoność czasowa?

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

Dlaczego każde wyszukiwanie oparte na porównaniach w posortowanej tablicy wymaga w najgorszym przypadku Ω(log n) porównań?

1. AKażde porównanie zajmuje czas logarytmiczny
2. BDrzewo decyzyjne z n możliwymi wynikami musi mieć głębokość co najmniej log₂ n
3. CKażdy element musi być porównany co najmniej raz
4. DWyszukiwanie binarne jest jedynym możliwym algorytmem i wymaga log₂ n porównań

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. AZawsze jest rozwiązywalne w O(V + E)
2. BJest nierozstrzygalne
3. CJest NP-trudne
4. DMożna je rozwiązać algorytmem Dijkstry z wagami o przeciwnym znaku