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

Що таке алгоритм?

1. AМова програмування, призначена для запису математичних формул
2. BСкінченна послідовність чітко визначених кроків, що розв'язує задачу
3. CБудь-яка комп'ютерна програма з графічним інтерфейсом
4. DСтруктура даних, що зберігає числа

Що таке базовий випадок рекурсивної функції?

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

Що описує час виконання алгоритму в найгіршому випадку?

1. AЧас на найменших вхідних даних
2. BМаксимальний час на всіх вхідних даних розміру n
3. CОчікуваний час на випадкових вхідних даних розміру n
4. DЧас на повільному комп'ютері

Що обчислює алгоритм Флойда–Воршелла і як швидко?

1. AМінімальне кістякове дерево за O(E log V)
2. BНайкоротші шляхи від однієї початкової вершини до всіх інших за O(V + E)
3. CНайкоротші шляхи між усіма парами вершин за O(V³)
4. DТопологічний порядок за O(V²)

Яка амортизована часова складність додавання елемента в кінець динамічного масиву, який подвоює свою місткість у разі заповнення?

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

Яка часова складність обчислення n-го числа Фібоначчі за допомогою таблиці знизу вгору?

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

Яка часова складність: for i = 1 to n: for (j = i; j ≤ n; j = j + i) виконати роботу O(1)?

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

Яке твердження про позначення «мале o» правильне?

1. A2n = o(n), бо 2n зростає повільно
2. Bn = o(n), бо кожна функція є «мале o» від самої себе
3. Cn² = o(n)
4. Dn = o(n²), але n не є o(n)