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

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

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

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

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

Що бінарний пошук вимагає від вхідних даних?

1. AМасив має містити не більше 1000 елементів
2. BМасив має містити лише додатні числа
3. CМасив має бути відсортованим
4. DДовжина масиву має бути степенем двійки

Яка часова складність алгоритму Беллмана–Форда на графі з V вершинами та E ребрами?

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

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

1. AОчікувану вартість на випадкових вхідних даних
2. BВартість однієї найдорожчої операції будь-де в послідовності
3. CВартість алгоритму на найкращих вхідних даних
4. DСередню вартість операції на послідовності операцій у найгіршому випадку

Функція виконує один цикл із n ітерацій, а потім окремо ще один цикл із n ітерацій. Яка її часова складність?

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

Які дві речі треба показати, щоб довести, що задача розпізнавання X є NP-повною?

1. AX належить до P, і X зводиться до SAT
2. BX належить до NP, і відома NP-повна задача зводиться до X за поліноміальний час
3. CX зводиться до задачі з P, і X належить до NP
4. DX не має поліноміального алгоритму, і X розв'язна

Сортування вставками працює за O(n) на відсортованих даних. Чи суперечить це нижній межі Ω(n log n) для сортування порівняннями?

1. AТак, але лише для масивів, коротших за 100
2. BНі, нижня межа стосується найгіршого випадку серед усіх вхідних даних, а не кожних вхідних даних
3. CТак, отже, нижня межа хибна
4. DНі, бо сортування вставками не є сортуванням порівняннями