Программа, использующая последовательный поиск, ищет элемент в массиве длины миллион в среднем за одну секунду. Сколько примерно времени потребуется на поиск, если мы заменим алгоритм поиска с последовательного на бинарный?

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

• # Сколько раз будет выполнено тело цикла в приведенной ниже программе? Многоточием обозначен фрагмент, не содержащий переменной x. int x = 100; while (x >= 0) { . . . x = x-1; }
• # Постановка задачи: программа должна содержать функцию, которая получает в качестве параметров имя массива и его длину (или нескольких массивов, если этого требуют условия задачи) и выполняет необходимые действия. При решении не разрешается создавать или резервировать в программе дополнительную память, соизмеримую по размерам с объемом исходных данных. То есть, нельзя создавать дополнительные массивы, если это явно не оговорено в задаче. Функция main должна заполнить массив числами из файла. Для определения длины массива предусматривается два варианта: 1) по значению первого числа в файле, 2) непосредственным подсчетом количества чисел в файле. Результат также выводится в файл. Задание: пусть в массиве последовательно записаны цифры некоторого длинного десятичного числа. Реализовать функции “прибавляющие единицу” и “вычитающие единицу” из такого числа. (для реализации переноса из “старшего разряда” можно заранее запасти 1 лишний элемент в массиве).
• # Выполняется ли инвариант цикла в процессе выполнения тела цикла?
• # Алгоритм быстрой сортировки реализован с помощью комбинированной схемы, использующей рекурсию и цикл 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? Дайте наиболее точную оценку снизу этого числа.
• # Алгоритм быстрой сортировки реализован с помощью комбинированной схемы, использующей рекурсию и цикл while; рекурсия применяется лишь к меньшему сегменту массива, разделенного на части функцией partition. Алгоритм применяется к массиву размером миллион. Может ли глубина рекурсии равняться 30?