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

Która z tych funkcji rośnie najwolniej, gdy n staje się duże?

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

Jak działa sortowanie przez wybieranie?

1. AWstawia każdy element do rosnącej posortowanej części przez przesuwanie
2. BWielokrotnie znajduje minimum nieposortowanej części i zamienia je na początek
3. CDzieli tablicę na połowy i je scala
4. DWielokrotnie zamienia sąsiednie elementy w złej kolejności

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

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

Ile pamięci stosu zużywa prosta rekurencyjna funkcja silni fact(n) = n × fact(n − 1)?

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

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

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

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²)
3. CΘ(n² log n)
4. DΘ(n^{log₂ 7}), około n^2,81

Czym różni się problem nierozstrzygalny od problemu praktycznie nierozwiązywalnego?

1. AProblemów praktycznie nierozwiązywalnych nie rozwiąże żaden algorytm, a nierozstrzygalne wymagają tylko czasu wykładniczego
2. BOba oznaczają, że problem w ogóle nie ma algorytmu
3. CProblemy nierozstrzygalne należą do NP, a praktycznie nierozwiązywalne do P
4. DProblem nierozstrzygalny nie ma algorytmu dla wszystkich danych; praktycznie nierozwiązywalny ma, ale jest zbyt wolny