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

Що таке рекурсія?

1. AЦикл, який ніколи не закінчується
2. BТип структури даних
3. CМетод сортування
4. DФункція, яка викликає саму себе для менших вхідних даних

Який час виконання сортування підрахунком для n цілих чисел у діапазоні від 0 до k?

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

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

1. A4 секунди
2. B2 секунди
3. C8 секунд
4. D1 секунду

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

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

Чи правильно казати, що алгоритм O(n²) є також O(n³)?

1. AНі, бо для великих n n³ менше за n²
2. BНі, бо «велике O» завжди має вказувати точну швидкість зростання функції
3. CТак, але лише якщо n менше за 100
4. DТак, бо «велике O» — верхня межа, а n² зростає не швидше, ніж n³

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

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

Для якого варіанта задачі про рюкзак жадібне правило «брати предмети в порядку цінності на одиницю ваги» завжди дає оптимальну відповідь?

1. AДля обох варіантів
2. BДля неперервного (дробового) рюкзака, де предмети можна ділити
3. CДля жодного варіанта
4. DДля рюкзака 0/1, де предмети завжди потрібно брати цілими

Який час виконання алгоритму Дейкстри з бінарною купою на графі з V вершинами та E ребрами?

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