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

Що таке рекурсія?

1. AФункція, яка викликає саму себе для менших вхідних даних
2. BЦикл, який ніколи не закінчується
3. CТип структури даних
4. DМетод сортування

Який клас складності зростає найшвидше для великих n?

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

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

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

Яка часова складність: for i = 1 to n: for j = 1 to i: виконати роботу O(1)?

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

Що означає, що задача має оптимальну підструктуру?

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

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

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

Сортування вставками працює за O(n) на відсортованих даних. Чи суперечить це нижній межі Ω(n log n) для сортування порівняннями?

1. AТак, отже, нижня межа хибна
2. BНі, нижня межа стосується найгіршого випадку серед усіх вхідних даних, а не кожних вхідних даних
3. CТак, але лише для масивів, коротших за 100
4. DНі, бо сортування вставками не є сортуванням порівняннями

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

1. A2-SAT, де кожен диз'юнкт має щонайбільше два літерали
2. BЗагальна SAT для формул у кон'юнктивній нормальній формі
3. CВиконуваність схем
4. D3-SAT, де кожен диз'юнкт має рівно три літерали