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

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

1. A9 секунд
2. B12 секунд
3. C3 секунди
4. D6 секунд

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

1. AСортування бульбашкою
2. BПірамідальне сортування
3. CСортування злиттям
4. DШвидке сортування (quicksort)

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

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

Чому динамічне програмування не дає реального пришвидшення для сортування злиттям?

1. AСортування злиттям уже має складність O(n)
2. BСортування злиттям не має рекурсивної структури
3. CДинамічне програмування працює лише на задачах про графи, а не на масивах
4. DЙого підзадачі не перекриваються, тож нічого використати повторно

Який розв'язок рекурентного співвідношення T(n) = 2T(n/2) + O(1)?

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

Що вимірює амортизований аналіз?

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)

Як алгоритм Беллмана–Форда виявляє цикл від'ємної ваги, досяжний із джерела?

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