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

Algorytm O(n²) działa 1 sekundę dla n = 1000. Ile mniej więcej będzie działał dla n = 2000?

1. A2 sekundy
2. B4 sekundy
3. C8 sekund
4. D1 sekundę

Algorytm O(n) działa 3 sekundy dla n = 1 milion. Ile mniej więcej będzie działał dla n = 2 miliony?

1. A12 sekund
2. B6 sekund
3. C9 sekund
4. D3 sekundy

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

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

Jak algorytm Prima buduje minimalne drzewo rozpinające?

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

W posortowanej tablicy szukasz dwóch elementów o sumie równej celowi, przesuwając po jednym wskaźniku z każdego końca do środka. Jaka jest złożoność czasowa?

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

Dlaczego wiele bibliotecznych procedur sortowania przełącza się na sortowanie przez wstawianie dla bardzo małych podtablic?

1. ASortowanie przez wstawianie ma mały narzut i jest szybkie dla małych lub prawie posortowanych danych
2. BSortowanie przez wstawianie jest O(n log n) w najgorszym przypadku
3. CSortowanie przez wstawianie zużywa mniej pamięci niż każdy inny algorytm sortowania dla dużych danych
4. DAlgorytmy rekurencyjne nie radzą sobie z tablicami poniżej 10 elementów

Jaka jest złożoność czasowa budowania kopca binarnego z n nieposortowanych elementów metodą wstępującą (bottom-up)?

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

Dlaczego średni czas wyszukiwania w tablicy mieszającej wynosi O(1), a w najgorszym przypadku O(n)?

1. ADostęp do tablic ma złożoność O(n)
2. BWiele kluczy może kolidować i trafić do tego samego kubełka
3. CKlucze muszą być najpierw posortowane
4. DFunkcje skrótu są wolne