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

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

1. AМаксимальний час на всіх вхідних даних розміру n
2. BЧас на повільному комп'ютері
3. CЧас на найменших вхідних даних
4. DОчікуваний час на випадкових вхідних даних розміру n

Що означає, що операція виконується за час O(1)?

1. AВона обробляє рівно один елемент за секунду часу виконання
2. BЇї час виконання не зростає з розміром вхідних даних
3. CЇї можна виконати лише один раз
4. DВона завжди триває рівно одну секунду

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

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

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

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

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

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

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

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

Топологічне сортування можливе лише для:

1. AПовних графів
2. BГрафів із від'ємними вагами
3. CОрієнтованих ациклічних графів
4. DНеорієнтованих графів

Узявши обидва кінці кожного ребра максимального (за включенням) паросполучення, отримують вершинне покриття. Наскільки воно добре?

1. AЗавжди мінімальне вершинне покриття
2. BЩонайбільше в log n разів більше за мінімум
3. CНевідомої якості порівняно з оптимумом
4. DЩонайбільше вдвічі більше за мінімальне вершинне покриття