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

Czym jest przypadek bazowy funkcji rekurencyjnej?

1. APrzypadkiem z największymi danymi wejściowymi, który obsługuje się przed jakimikolwiek wywołaniami rekurencyjnymi
2. BWywołaniem zużywającym najwięcej pamięci
3. CPrzypadkiem, na który odpowiada się bezpośrednio, bez kolejnego wywołania rekurencyjnego
4. DPierwszym wierszem funkcji

Dostęp do elementu tablicy po indeksie zajmuje:

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

Ile dodatkowej pamięci używa standardowe sortowanie przez scalanie oparte na tablicach?

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

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

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

Dlaczego w notacji dużego O zwykle pomija się podstawę logarytmu, jak w O(log n)?

1. ALogarytmy zawsze zaokrągla się do liczb całkowitych
2. BWszystkie logarytmy w informatyce mają podstawę 10, więc jest ona domyślna
3. CLogarytmy o różnych podstawach różnią się tylko stałym czynnikiem
4. DPodstawa ma znaczenie tylko dla małych n

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

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

Dlaczego wyszukiwanie binarne nie daje czasu O(log n) na liście jednokierunkowej?

1. APorównania na węzłach listy są wolniejsze
2. BDotarcie do środkowego elementu wymaga O(n) kroków, bo nie ma bezpośredniego dostępu po indeksie
3. CList nie da się posortować
4. DWyszukiwanie binarne wymaga co najmniej dwa razy więcej pamięci