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

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

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

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

1. AЖадібний вибір
2. BДинамічне програмування
3. CПовний перебір
4. D«Розділяй і володарюй»

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

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

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

1. AВона автоматично повертає 0
2. BВона виконується за час O(1)
3. CВона викликає себе, доки не переповниться стек викликів
4. DКомпілятор завжди перетворює її на цикл, що безпечно завершується

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

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

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

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

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

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

Чому пошук у геш-таблиці в середньому має складність O(1), а в найгіршому випадку — O(n)?

1. AБагато ключів через колізії можуть потрапити в один і той самий кошик
2. BДоступ до масивів має складність O(n)
3. CКлючі спершу потрібно відсортувати
4. DГеш-функції повільні