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

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

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

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

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

Який час виконання сортування підрахунком для n цілих чисел у діапазоні від 0 до k?

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

Яка часова складність: 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)

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

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

Чому багато бібліотечних процедур сортування переходять на сортування вставками для дуже малих підмасивів?

1. AСортування вставками має складність O(n log n) у найгіршому випадку
2. BРекурсивні алгоритми не можуть обробляти масиви менші за 10 елементів
3. CСортування вставками має малі накладні витрати й швидке на малих або майже відсортованих даних
4. DСортування вставками використовує менше пам'яті, ніж будь-який інший алгоритм сортування, на великих даних

Яке твердження про P і NP є правильним?

1. AДоведено, що P ≠ NP
2. BРозв'язки задач NP неможливо швидко перевірити
3. CКожна задача з P також належить до NP
4. DNP означає «неполіноміальний» (not polynomial)

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

1. AO(1) на інкремент
2. BO(n log n) на інкремент
3. CO(n) на інкремент
4. DO(log n) на інкремент