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

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

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

Яке позначення описує нижню межу зростання?

1. Ao (мале o)
2. BΘ (велике Тета)
3. CΩ (велике Омега)
4. DO (велике O)

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

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

Швидке сортування завжди бере опорним перший елемент. На яких вхідних даних воно демонструє поведінку найгіршого випадку?

1. AНа масиві довжини 2
2. BНа масиві у випадковому порядку
3. CНа вже відсортованому масиві
4. DНа масиві, всі елементи якого різні

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

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

Який алгоритм сортування є стійким?

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

Як класифікують задачу комівояжера?

1. AВона належить до P, бо її розв'язує алгоритм Дейкстри, відвідуючи кожне місто один раз
2. BВерсія розпізнавання належить до P, а оптимізаційна — NP-повна
3. CВона нерозв'язна
4. DВерсія розпізнавання є NP-повною, а оптимізаційна версія — NP-складною

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

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