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

Яка нотація описує верхню межу зростання?

1. AВелике O
2. BВелике Омега
3. CВелике Тета
4. DМале омега

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

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

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

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

Яка часова складність множення двох матриць n × n стандартним потрійним циклом?

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

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

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

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

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

Чи належить 2²ⁿ до O(2ⁿ)?

1. AНі, бо 2²ⁿ = 4ⁿ, а 4ⁿ / 2ⁿ = 2ⁿ зростає необмежено
2. BТак, бо сталі множники в показнику степеня в нотації «велике O» завжди ігноруються
3. CТак, бо обидві функції експоненційні
4. DНі, бо 2²ⁿ зростає повільніше, ніж 2ⁿ

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

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