RADIX-сортировка применяется к составным ключам длины k, длина сортируемого массива равна n. Какова асимптотическая оценка времени работы алгоритма?

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

• # В алгоритме получения записи числа n в системе счисления с основанием b мы вычисляем цифры числа справа налево, начиная с последней цифры. На очередном шаге мы делим n с остатком на b, получая частное q и остаток r; остаток представляет очередную цифру числа в порядке справа налево. Затем мы переменной n присваиваем значение частного q, и процесс повторяется, пока n не станет равным нулю. Сколько раз будет выполнена операция деления при переводе числа 2000000 (два миллиона) в восьмеричную систему счисления?
• # Рассмотрим реализацию матрицы вещественных чисел размера m строк на n столбцов при помощи линейного массива, в котором хранятся сначала элементы нулевой строки матрицы, затем первой и т.д., в конце - элементы (m-1)-й строки: int m, n; // Размеры матрицы: число строк, столбцов . . . double* a = new double[m*n]; // a[i*n + j] -- элемент i-й строки и j-го столбца Пусть функция с прототипом void transp(double* a, int m, int n); реализует транспонирование матрицы, при выполнении которого строки матрицы становятся столбцами, столбцы - строками, а матрица размера m на n превращается в матрицу размера n на m Пусть эта функция применяется к прямоугольной матрице, содержащей 3 строки и 5 столбцов, элементы которой хранятся в линейном массиве a. Сколько элементов массива a при этом останутся на своем месте?
• # Пусть переменные a, p, q, n описаны следующим образом: double a[10]; double *p; const double *q; int n; Отметьте, какие из приведенных ниже операторов языка C/C++ корректны.
• # Пусть целочисленная переменная n содержит некоторое положительное целое число. Указать, что вычисляет следующая функция f(n): int f(int n) { int s = 2; int k = 0; while (s <= n) { // Invariant: s == 2^(k+1) s *= 2; ++k; } return k; }
• # Алгоритм быстрой сортировки реализован с помощью комбинированной схемы, использующей рекурсию и цикл 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 при выполнении алгоритма быстрой сортировки для массива размера 95? Дайте наиболее точную оценку снизу этого числа.