Робочий аркуш «Алгоритми та складність» з відповідями

Яка часова складність лінійного пошуку в невідсортованому масиві з n елементів (у найгіршому випадку)?

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

Яка оцінка «велике O» для 3n² + 5n + 2?

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

Що означає f(n) = Θ(g(n))?

1. Af зростає строго швидше, ніж g
2. Bf завжди менша за g для кожного n, тож g обмежує її зверху, але ніколи знизу
3. Cf зростає з тією самою швидкістю, що й g, обмежена зверху й знизу сталими кратними g
4. Df зростає строго повільніше, ніж g

Яка часова складність алгоритму Беллмана–Форда на графі з V вершинами та E ребрами?

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

Яка часова складність: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

Як алгоритм Прима будує мінімальне кістякове дерево?

1. AВін сортує всі ребра за вагою й додає кожне, окрім тих, що утворили б цикл у лісі
2. BВін вирощує одне дерево від початкової вершини, додаючи найдешевше ребро, що виходить із дерева
3. CВін запускає пошук у ширину й зберігає дерево BFS
4. DВін видаляє найдорожче ребро, доки не залишиться циклів

Яка різниця між нерозв'язною задачею та практично нерозв'язною?

1. AНерозв'язні задачі належать до NP, а практично нерозв'язні — до P
2. BОбидва терміни означають, що задача взагалі не має алгоритму
3. CПрактично нерозв'язні задачі не може розв'язати жоден алгоритм, а нерозв'язні лише потребують експоненційного часу
4. DДля нерозв'язної задачі немає алгоритму для всіх вхідних даних; для практично нерозв'язної він є, але надто повільний

Яка часова складність побудови бінарної купи з n невідсортованих елементів висхідним методом (bottom-up)?

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