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

Jaka jest złożoność czasowa przeszukiwania w głąb grafu zapisanego jako listy sąsiedztwa?

1. AO(E log V)
2. BO(V × E)
3. CO(V²)
4. DO(V + E)

Jaka jest optymistyczna złożoność czasowa sortowania przez wstawianie dla już posortowanej tablicy?

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

Co opisuje średni czas działania?

1. ACzas na najpopularniejszym komputerze
2. BCzas dla danych o przeciętnej długości
3. CWartość pośrodku między czasami działania w przypadku optymistycznym a pesymistycznym
4. DOczekiwany czas przy danym rozkładzie danych wejściowych rozmiaru n

Które stwierdzenie o funkcji rekurencyjnej bez osiągalnego przypadku bazowego jest poprawne?

1. AKompilator zawsze zamienia ją na pętlę, która kończy się bezpiecznie
2. BDziała w czasie O(1)
3. CAutomatycznie zwraca 0
4. DWywołuje samą siebie, aż przepełni się stos wywołań

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

1. APodstawa ma znaczenie tylko dla małych n
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. DLogarytmy zawsze zaokrągla się do liczb całkowitych

Jaka jest złożoność czasowa algorytmu Bellmana–Forda dla grafu o V wierzchołkach i E krawędziach?

1. AO(V + E)
2. BO(E log V)
3. CO(V³ × E)
4. DO(V × E)

Co ustaliło twierdzenie Cooka–Levina?

1. AP nie jest równe NP
2. BProblem stopu jest nierozstrzygalny
3. CProblem spełnialności formuł logicznych (SAT) jest NP-zupełny
4. DKażdy problem NP można rozwiązać w czasie wykładniczym

Algorytm programowania dynamicznego Helda–Karpa rozwiązuje dokładnie problem komiwojażera. Jaki jest jego czas działania dla n miast?

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