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

Що таке мемоізація?

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

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

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

Що означає, що операція виконується за час O(1)?

1. AЇї час виконання не зростає з розміром вхідних даних
2. BВона завжди триває рівно одну секунду
3. CЇї можна виконати лише один раз
4. DВона обробляє рівно один елемент за секунду часу виконання

Приблизно скільки порівнянь потребує бінарний пошук у найгіршому випадку на відсортованому масиві з 1,000,000 елементів?

1. AБлизько 500,000
2. BБлизько 100
3. CБлизько 1,000
4. DБлизько 20

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

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

Що означає, що задача має оптимальну підструктуру?

1. AУсі підзадачі мають однаковий розмір
2. BЗадача має рівно один оптимальний розв'язок, спільний для кожної підзадачі
3. CОптимальний розв'язок можна побудувати з оптимальних розв'язків її підзадач
4. DЗадачу можна розв'язати за сталий час

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

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

Яка амортизована вартість інкременту двійкового лічильника, якщо один інкремент може змінити багато бітів?

1. AO(n) на інкремент
2. BO(log n) на інкремент
3. CO(1) на інкремент
4. DO(n log n) на інкремент