при поиске максимального элемента в массиве из N элементов попадается новый элемент, больший, чем текущий максимальный, асимптотически равно ln(N). Провести численный эксперимент, подтверждающий данную оценку. Для этого для каждого значения N из множества {10, 100, 1000, 10000, 100000 и 1000000} сгенерировать некоторое количество массивов длины N, в которых случайным образом распределены натуральные числа, подсчитать сколько раз найдется элемент больший текущего максимального и усреднить по всем массивам данной длины. Построить график зависимости найденного среднего значения от размера массива, на том же графике отложить теоретическую кривую. Для оси x использовать логарифмический масштаб.
Но у меня раз на раз не приходится и отклонения от lnN могут быть достаточно большими. С чем это связано? с rand? И как это исправить? Помогите, пожалуйста!
https://pastebin.com/Jzeniiyg
Поможете?
Обсуждают сегодня