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

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

1. A3 секунди
2. B9 секунд
3. C6 секунд
4. D12 секунд

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

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

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

1. AO(E log V)
2. BO(V²)
3. CO(V + E)
4. DO(V × E)

Маючи монети номіналом 1, 3 і 4 та суму 6, скільки монет використовує жадібний метод «спершу найбільша монета» порівняно з оптимумом?

1. AЖадібний використовує 3 монети; оптимум — 2
2. BЖадібний використовує 4 монети; оптимум — 3
3. CЖадібний використовує 3 монети; оптимум — 3
4. DЖадібний використовує 2 монети; оптимум — 2

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

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

Яке жадібне правило в задачі про вибір заявок (activity selection) завжди дає максимальну кількість заявок, що не перекриваються?

1. AОбрати заявку, що закінчується найраніше, а потім повторити із сумісними
2. BОбрати заявку, що починається найраніше
3. CСпершу обрати заявку з найменшою кількістю перекриттів, а потім повторити із сумісними
4. DСпершу обрати найкоротшу заявку

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

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

Чому бінарний пошук не дає часу O(log n) на однозв'язному списку?

1. AЗв'язні списки неможливо сортувати
2. BБінарному пошуку потрібно щонайменше вдвічі більше пам'яті
3. CПорівняння вузлів зв'язного списку повільніші
4. DЩоб дістатися середнього елемента, потрібно O(n) кроків, бо немає прямого доступу за індексом