Какие из перечисленных ниже алгоритмов сортировки работают в среднем за время O(n log₂ n)? Отметьте все правильные ответы.

Правильный ответ:

• # При вычислении (x+y)7 раскрываются скобки и приводятся подобные члены. Чему будет равен коэффициент при x3y4?
• # Формула Бинома Ньютона дает следующее разложение в ряд для функции "квадратный корень из z": (1+x)0.5 = sqrt(1+x) = 1 + 0.5 x + 0.5(-0.5)/2! x2 + 0.5(-0.5)(-1.5)/3! x3 + 0.5(-0.5)(-1.5)(-2.5)/4! x4 + ... (мы обозначили z=1+x). Рассмотрим реализованную на C/C++ функцию mySqrt(z), вычисляющую значение квадратного корня с точностью до одной миллионной: static const double EPS = 1e-6; double mySqrt(double z) { double x = z - 1.; double s = 1; double k = 0.5; double n = 1.; double a = k*x; while (fabs(a) > eps) { s += a; k -= 1.; n += 1.; a *= (k/n)*x; } return s; } Для каких значений z ее можно применять так, чтобы функция завершала работу за разумное время и ошибка вычисления результата была бы не более 0.0001? Укажите все правильные ответы из числа перечисленных ниже.
• # Пусть функция f(x) = p*x2 + q*x + r (многочлен степени 2) задана на отрезке [a, b]. Пусть отрезок [a, b] разделен на 4 равных части; обозначим концы этих отрезков через x0, x1, x2, x3, x4: h = (b-a)/4, xi = a+i*h, i = 0,1,2,3,4. Обозначим yi = f(xi). Чему равен интеграл функции f(x) по отрезку [a, b]? Отметьте все правильные ответы.
• # Мы хотим реализовать функцию product, которая находит произведение элементов вещественного массива a длины n. Отметьте, какие из возможных прототипов данной функции корректны.
• # Программа, использующая последовательный поиск, ищет элемент в массиве длины миллион в среднем за одну секунду. Сколько примерно времени потребуется на поиск, если мы заменим алгоритм поиска с последовательного на бинарный?