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

Jaka jest złożoność czasowa wyszukiwania liniowego w nieposortowanej tablicy n elementów (w najgorszym przypadku)?

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

Który z tych czasów działania jest wielomianowy?

1. AO(n³)
2. BO(nⁿ)
3. CO(n!)
4. DO(2ⁿ)

Który algorytm sortowania wielokrotnie zamienia miejscami sąsiednie elementy ustawione w złej kolejności?

1. ASortowanie przez scalanie
2. BSortowanie szybkie (quicksort)
3. CSortowanie przez kopcowanie
4. DSortowanie bąbelkowe

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

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

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

Jaka jest złożoność czasowa: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Który z tych problemów spełnialności jest rozwiązywalny w czasie wielomianowym?

1. A2-SAT, w którym każda klauzula ma najwyżej dwa literały
2. BOgólny SAT dla formuł w koniunkcyjnej postaci normalnej
3. C3-SAT, w którym każda klauzula ma dokładnie trzy literały
4. DSpełnialność układów logicznych (circuit SAT)

Sortowanie topologiczne jest możliwe tylko dla:

1. ASkierowanych grafów acyklicznych
2. BGrafów nieskierowanych
3. CGrafów pełnych
4. DGrafów z ujemnymi wagami