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

Dostęp do elementu tablicy po indeksie zajmuje:

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

Jakie są trzy kroki algorytmu typu dziel i zwyciężaj?

1. AZgadnij, sprawdź, powtórz
2. BSortuj, szukaj, zwróć
3. CWczytaj, oblicz, zapisz
4. DPodziel, zwycięż, połącz

Pętla zaczyna od i = 1 i w każdej iteracji podwaja i, aż do chwili, gdy i > n. Ile iteracji wykona?

1. AOkoło log₂ n
2. BOkoło n²
3. COkoło n / 2
4. DOkoło n

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

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

Ile poziomów ma rekurencja sortowania przez scalanie dla tablicy n elementów?

1. AOkoło √n
2. BOkoło n / 2
3. COkoło n
4. DOkoło log₂ n

Dolne ograniczenie dla sortowania opartego na porównaniach w najgorszym przypadku wynosi:

1. AΩ(n)
2. BΩ(n log n)
3. CΩ(n²)
4. DΩ(log n)

Problem stopu pokazuje, że:

1. ANiektóre programy działają szybciej na szybszych komputerach, więc zatrzymanie zależy od sprzętu
2. BŻaden algorytm nie może rozstrzygnąć dla każdego programu i danych wejściowych, czy program się zatrzyma
3. CNależy unikać pętli
4. DKażdy program w końcu się zatrzymuje

Algorytm Strassena mnoży macierze, używając 7 zamiast 8 rekurencyjnych mnożeń bloków o połowie rozmiaru. Jaki jest jego czas działania?

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