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

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

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

Która notacja opisuje górne ograniczenie tempa wzrostu?

1. ANotacja małe omega
2. BNotacja duże Theta
3. CNotacja duże Omega
4. DNotacja duże O

Co oznacza f(n) = Θ(g(n))?

1. Af rośnie w tym samym tempie co g, ograniczona z góry i z dołu stałymi wielokrotnościami g
2. Bf rośnie ściśle szybciej niż g
3. Cf rośnie ściśle wolniej niż g
4. Df jest zawsze mniejsza niż g dla każdego n, więc g ogranicza ją od góry, lecz nigdy od dołu

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

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

Jaka jest złożoność czasowa standardowego algorytmu programowania dynamicznego dla najdłuższego wspólnego podciągu napisów o długościach m i n?

1. AO(mn log n)
2. BO(2^m+n)
3. CO(mn)
4. DO(m + n)

Programowanie dynamiczne jest przydatne, gdy problem ma:

1. APojedynczą pętlę
2. BWyłącznie losowe dane wejściowe
3. CNakładające się podproblemy i optymalną podstrukturę
4. DŻadnych podproblemów, więc można go rozwiązać w jednym kroku

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

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

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

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