Статья 2301

С помощью эксперимента ответить на вопрос нельзя. Имеется возможных перестановок данных чисел, что для проверки слишком много даже при небольших значениях. При массиве всего из 16 элементов и компьютере, способном проверить миллион вариантов перестановок в секунду, полный анализ занял бы более полугода.
Аналитический метод определения искомого среднего довольно прост. Присваивание начального значения выполняется всегда, поэтому подсчет исполнений начнем. Предположим, что все перестановки равновероятны. Тогда вероятность того, что второй элемент больше первого, равна половине вероятности того, что третий элемент больше любого из первых двух элементов, равна одной трети. Этот анализ можно продолжить, так что среднее число присваиваний будет равно сумме, которая называется гармоническим рядом. Математик XVIII в. Леонард Эйлер показал, что сумма этого ряда приблизительно равняется натуральному логарифму плюс константа, называемая теперь постоянной Эйлера ее значение равно приблизительно 0,577. Логарифм растет намного медленнее, чем само, поэтому время, расходуемое на присваивание переменной новых значений, пренебрежимо мало по отношению ко времени, затрачиваемому на проведение сравнений и увеличение индекса массива. Следовательно, есть основание говорить о том, что объем работы, необходимой для нахождения максимального из чисел, пропорционален.
Большинство практических задач не поддается столь же легкому исследованию, поэтому анализ алгоритмов является областью активного изучения. Во многих случаях достаточно знать, как зависит время расчета от некоторого характерного размера задачи. Например, время может расти и пропорционально самому размеру, и пропорционально квадрату размера, а иногда и экспоненциально экспоненциальный рост делает алгоритм почти неприменимым.