Алгоритм быстрой сортировки реализован с помощью комбинированной схемы, использующей рекурсию и цикл while, а также вспомогательную функцию partition, которая разделяет текущий отрезок массива на 3 части (элементы, меньшие либо равные медиане, медиана, элементы, большие либо равные медиане): void quickSort(double* a, int n) { if (n <= 1) { return; } else if (n == 2) { if (a[0] > a[1]) swap(&(a[0]), &(a[1])); return; } int beg = 0; int k = n; while (k > 1) { int m = k / 2; partition(a+beg, k, &m); int left = m; int right = k - left - 1; if (left <= right) { // Рекурсивно применяем алг. к левой части quickSort(a+beg, left); beg += left + 1; k -= left + 1; } else { // Рекурсивно применяем алг. к правой части quickSort(a+beg+m+1, right); k -= right + 1; } } } Сколько раз будет вызвана функция partition при выполнении алгоритма быстрой сортировки для массива размера 47? Дайте наиболее точную оценку снизу этого числа.

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

• # Рассмотрим 8 байтов, в которых записан некоторый двочный код. Всегда ли он представляет вещественное число, записанное в плавающей форме, т.е. значение типа double?
• # Пусть неизвестная функция определена на отрезке [a, b], причем на концах отрезка заданы ее значения y0=f(a), y1=f(b), а также значения ее производной y'0=f'(a), y'1=f'(b). Нужно приблизить функцию многочленом так, чтобы на концах отрезка его значения, а также значения его производной совпадали со значениями и производной функции. Какой должна быть степень такого многочлена? (Укажите минимальную степень, достаточную для решения этой задачи.)
• # Какой объект описан в следующей строке программы на C/C++? double a[20][30];
• # Пусть целочисленная переменная n содержит некоторое положительное целое число. Указать, что вычисляет следующая функция f(n): int f(int n) { int x = 1; int y = 4; while (y <= n) { // Invariant: y == (x+1)^2 ++x; y += 2*x+1; } return x; }
• # Пусть мы имеем набор из n элементов, которые можно сравнивать между собой. Их медианой называется такое значение m, что число элементов набора, меньших либо равных m, равно числу элементов, больших либо равных m. Существует ли алгоритм выбора медианы, который работает за время O(n) (т.е. за время, линейно зависящее от n)?