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

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

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

Алгоритм O(n) працює 3 секунди для n = 1 мільйон. Приблизно скільки він працюватиме для n = 2 мільйони?

1. A9 секунд
2. B3 секунди
3. C12 секунд
4. D6 секунд

Час виконання алгоритму — O(n). Як називається таке зростання?

1. AКвадратичне
2. BЛогарифмічне
3. CЛінійне
4. DСтале

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

1. AБлизько n
2. BБлизько log₂ n
3. CБлизько √n
4. DБлизько n / 2

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

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

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

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

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

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

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

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