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

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

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

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

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

Який клас складності зростає найшвидше для великих n?

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

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

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

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

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

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

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

Як алгоритм Беллмана–Форда виявляє цикл від'ємної ваги, досяжний із джерела?

1. AВін підраховує цикли пошуком у глибину
2. BПісля V − 1 раундів він перевіряє, чи можна ще релаксувати якесь ребро
3. CВін перевіряє, чи має якесь ребро від'ємну вагу
4. DВін двічі запускає алгоритм Дейкстри й порівнює два результати відстаней

Яке твердження про позначення «мале o» правильне?

1. An = o(n²), але n не є o(n)
2. Bn = o(n), бо кожна функція є «мале o» від самої себе
3. Cn² = o(n)
4. D2n = o(n), бо 2n зростає повільно