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

Яка часова складність бінарного пошуку у відсортованому масиві?

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

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

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

Скільки додаткової пам'яті використовує стандартне сортування злиттям на основі масиву?

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

Який алгоритм знаходить найкоротші шляхи з одного джерела в графі з невід'ємними вагами ребер?

1. AАлгоритм Дейкстри
2. BПошук у глибину (DFS)
3. CУ всіх випадках потрібен алгоритм Беллмана–Форда
4. DАлгоритм Краскала

Який час виконання порозрядного сортування LSD для n цілих чисел із d цифрами в системі числення з основою k?

1. AO(dn log k)
2. BO(d(n + k))
3. CO(n log n)
4. DO(n²)

Чому багато бібліотечних процедур сортування переходять на сортування вставками для дуже малих підмасивів?

1. AРекурсивні алгоритми не можуть обробляти масиви менші за 10 елементів
2. BСортування вставками має складність O(n log n) у найгіршому випадку
3. CСортування вставками використовує менше пам'яті, ніж будь-який інший алгоритм сортування, на великих даних
4. DСортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних

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

1. AАлгоритм Дейкстри
2. BАлгоритм Краскала
3. CАлгоритм Флойда–Воршелла
4. DАлгоритм Прима, що починає з однієї вершини

Задача про рюкзак 0/1, розв'язана динамічним програмуванням, потребує O(nW) часу. Чому це називають псевдополіноміальним часом?

1. AТому що n завжди мале
2. BТому що алгоритм рандомізований, а його час роботи змінюється для кожних вхідних даних
3. CW — число, тому час експоненційний відносно кількості бітів, використаних для запису W
4. DТому що він працює лише для W = 0