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

Цикл починається з i = 1 і подвоює i на кожній ітерації, доки i > n. Скільки ітерацій він виконує?

1. AБлизько n / 2
2. BБлизько n
3. CБлизько log₂ n
4. DБлизько n²

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

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

Який алгоритм сортування багаторазово міняє місцями сусідні елементи, що стоять у неправильному порядку?

1. AШвидке сортування (quicksort)
2. BСортування злиттям
3. CПірамідальне сортування
4. DСортування бульбашкою

Скільки пам'яті стека використовує проста рекурсивна функція факторіала fact(n) = n × fact(n − 1)?

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

Ви один раз сортуєте масив із n елементів, а потім відповідаєте на k запитів про належність бінарним пошуком. Яка загальна вартість?

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

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

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

Найкоротші прості шляхи можна знайти за поліноміальний час. Що відомо про пошук найдовшого простого шляху між двома вершинами в загальному графі?

1. AЦе NP-складна задача
2. BЇї можна розв'язати алгоритмом Дейкстри з від'ємними вагами
3. CВона нерозв'язна
4. DЇї завжди можна розв'язати за O(V + E)

Чому будь-який пошук порівняннями у відсортованому масиві потребує Ω(log n) порівнянь у найгіршому випадку?

1. AБінарний пошук — єдиний можливий алгоритм, і йому потрібно log₂ n порівнянь
2. BКожне порівняння триває логарифмічний час
3. CКожен елемент треба порівняти щонайменше один раз
4. DДерево рішень з n можливими результатами має глибину щонайменше log₂ n