Контрольная работа 1

1. Верно ли, что число сравнений, требуемых алгоритмом бинарного поиска места элемента в упорядоченном массиве длины n, однозначно определяется n?

1. Верно ли, что сложность T_A(n) всегда больше затрат C_A(x)? (A – некоторый алгоритм, x – вход, n – размер входа x)

1. Возможно ли, что равенство (x) + 1 = T_A(n), где x – вход, n – размер входа x, для затрат n сложности по числу каких-то операций некоторого алгоритма A выполняется при всех входах x?

1. Хорошо известно, что сложность алгоритма сортировки бинарными вставками по числу сравнений в худшем случае, применяемого к массиву длины n, допускает оценки

1) n log ₂ n + O(n) 2) (n log n) 3) (n log n)

1. из какой оценки (указать номер) следуют две остальные?

2. можно ли среди приведённых оценок выбрать такую, которая является следствием любой из остальных? Если да, то указать номера всех таких оценок

3. является ли оценка O(n log n) следствием какой-либо из оценок 1), 2), 3)? Если да, то указать номера всех таких оценок.

1. Верно ли, что сложность (число сравнений, требуемое в худшем случае) алгоритма бинарного поиска места элемента в упорядоченном массиве длины n допускает оценку O( )?

1. Алгоритм, использующий только аддитивные операции и сравнение целых чисел для проверки того, является ли данное натуральное n точным квадратом, может быть основан на вычислении последовательности значений 1+3, 1+3+5, … до появления в ней первого большего или равного n элемента. Сложность по числу аддитивных операций и операций сравнения этого алгоритма допускает оценку ( ). Сохранится ли эта оценка, если дополнительно использовать операцию нахождения целой части половины числа (считается, что затратность этой операции такая же, как у аддитивных операций) для того, чтобы предварительно выяснить, на какую степень двойки – чётную или нечётную, делится n?

1. Пусть A – некоторый алгоритм сортировки массивов, и n обозначает длину (число элементов) входного массива. Пусть , (n) – сложность алгоритма A как затраты в худшем случае и в среднем по числу сравнений. Может ли быть так, что для достаточно больших n выполняется

1. Верно ли, что сложность в среднем рандомизированной быстрой сортировки по числу обращений к генератору случайных чисел есть (n log n)?

1. Верно ли, что определение усреднённых затрат некоторого рандомизированного алгоритма требует задания распределения вероятностей на каждом из множеств всех входов фиксированного размера?

1) нет, 2) нет, 3) нет, 4) a-1 b-2 c-1,3, 5) да, 6) да, 7) a-да b-да, 8) нет, 9) да