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

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

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

Доступ до елемента масиву за індексом займає:

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

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

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

Яка часова складність: for i = 1 to n: (j = 1; while j < n: j = j × 2)?

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

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

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

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

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

Що випливало б, якби хтось знайшов поліноміальний алгоритм для однієї NP-повної задачі?

1. AЛише ця одна задача перейшла б до P
2. BПроблема зупинки стала б розв'язною
3. CКожну задачу з NP можна було б розв'язати за поліноміальний час, тож P = NP
4. DУсі алгоритми з експоненційним часом негайно стали б працювати за лінійний час

Чому пошук у геш-таблиці в середньому має складність O(1), а в найгіршому випадку — O(n)?

1. AКлючі спершу потрібно відсортувати
2. BГеш-функції повільні
3. CДоступ до масивів має складність O(n)
4. DБагато ключів через колізії можуть потрапити в один і той самий кошик