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

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

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

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

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

Що з наведеного зростає найповільніше зі збільшенням n?

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

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

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

Який алгоритм знаходить найкоротші шляхи з одного джерела в графі з невід'ємними вагами ребер?

1. AУ всіх випадках потрібен алгоритм Беллмана–Форда
2. BАлгоритм Краскала
3. CПошук у глибину (DFS)
4. DАлгоритм Дейкстри

Пошук у ширину в незваженому графі знаходить:

1. AМінімальне кістякове дерево
2. BТопологічний порядок у будь-якому графі
3. CНайкоротші шляхи в графах, що містять ребра з від'ємними вагами
4. DНайкоротші шляхи (за кількістю ребер) від початкової вершини

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

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

За основною теоремою (master theorem) розв'язком T(n) = 8T(n/2) + O(n²) є:

1. AΘ(n³)
2. BΘ(n² log n)
3. CΘ(n²)
4. DΘ(n log n)