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

Як називається зростання O(2ⁿ)?

1. AЛінійне
2. BПоліноміальне
3. CЛогарифмічне
4. DЕкспоненційне

Чому дорівнює log₂ 1024?

1. A32
2. B512
3. C10
4. D12

Що таке алгоритм повного перебору?

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

Жадібний алгоритм:

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

Скільки пам'яті стека використовує проста рекурсивна функція факторіала fact(n) = n × fact(n − 1)?

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

Ви один раз сортуєте масив із n елементів, а потім відповідаєте на k запитів про належність бінарним пошуком. Яка загальна вартість?

1. AO(n + k)
2. BO(k n log n)
3. CO(n log n + k log n)
4. DO(nk)

Сортування вставками працює за O(n) на відсортованих даних. Чи суперечить це нижній межі Ω(n log n) для сортування порівняннями?

1. AТак, але лише для масивів, коротших за 100
2. BТак, отже, нижня межа хибна
3. CНі, нижня межа стосується найгіршого випадку серед усіх вхідних даних, а не кожних вхідних даних
4. DНі, бо сортування вставками не є сортуванням порівняннями

Найкоротші прості шляхи можна знайти за поліноміальний час. Що відомо про пошук найдовшого простого шляху між двома вершинами в загальному графі?

1. AЇї можна розв'язати алгоритмом Дейкстри з від'ємними вагами
2. BЦе NP-складна задача
3. CЇї завжди можна розв'язати за O(V + E)
4. DВона нерозв'язна