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

Що з наведеного зростає найповільніше зі збільшенням n?

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

Що таке базовий випадок рекурсивної функції?

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

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

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

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

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

Часова складність наївного рекурсивного обчислення чисел Фібоначчі (fib(n) = fib(n−1) + fib(n−2)) є:

1. AЕкспоненційною
2. BЛогарифмічною
3. CСталою
4. DЛінійною

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

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

Яке визначення класу NP правильне?

1. AЗадачі, які не може розв'язати жоден алгоритм
2. BЗадачі, які неможливо розв'язати за поліноміальний час
3. CЗадачі, що не є поліноміальними
4. DЗадачі розпізнавання, відповіді «так» для яких можна перевірити за поліноміальний час за наявності сертифіката

Яке визначення класу P правильне?

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