Почему мои двоичные вставки в кучу ведут себя так на практике?
Я реализовал в C ++ двоичную кучу на основе массива и двоичную кучу на основе указателя. Я провел небольшой эксперимент, в котором для разных входных размеров n я сделал n вставок. Элементы имеют тип int32_t, и каждый из них выбирается случайным образом (с мерсенновским твистером) из
{1,...,std::numeric_limits<int32_t>::max()}
Поэтому я запускал каждый эксперимент 10 раз и брал среднее время процессора, необходимое для завершения эксперимента.
Для вычисления времени процессора я использовал следующие функции:
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
а также
clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);
Вот время работы
Мне кажется, что для вставки n элементов требуется линейное время вместо времени nlogn. Если я разделю время выполнения на n, я получу следующий график:
Оба времени работы сходятся к постоянной. Так что это подтверждает мое предположение.
Но почему? Разве это не должно сходиться к логарифмической функции? Разве не каждая вставка O (logn)?
Решение
Это правда, что ожидаемый время для создания двоичной кучи из случайных данных путем повторной вставки O(n)хотя время наихудшего случая (когда вход отсортирован) O(n log n), Этот интересный результат был известен в течение некоторого времени, хотя он, по-видимому, широко не известен, по-видимому, из-за популярности широко известного алгоритма гарантированного линейного времени с кучей благодаря Р. В. Флойду.
Интуитивно можно ожидать, что среднее время вставки для случайных элементов будет равно O (1), исходя из предположения, что случайно построенная куча аппроксимирует полное двоичное дерево. Алгоритм вставки состоит в размещении элемента в конце кучи и последующем его продвижении путем многократной замены его родителем до тех пор, пока не будет выполнено ограничение кучи.
Если бы куча была полным двоичным деревом, то среднее время вставки действительно было бы равно O (1), поскольку в каждой точке цепочки свопов вероятность того, что потребуется еще один своп, была бы равна 0,5. Таким образом, в половине случаев обмен не требуется; в четверти времени требуется один своп, в восьмой — два; и так далее. Следовательно, ожидаемое количество свопов составляет 0 + 0,5 + 0,25 + … == 1.
Поскольку куча является лишь приближением полного двоичного дерева, приведенный выше анализ недостаточен. Невозможно поддерживать бинарное дерево без перебалансировки, что имеет нетривиальные затраты. Но вы можете продемонстрировать, что куча достаточно похожа на двоичное дерево, что ожидаемое время вставки все еще равно O (1). Доказательство нетривиально; один анализ, доступный в режиме онлайн, — это «Анализ среднего случая построения кучи с помощью повторных вставок» (1991) Райана Хейворда и Колина Макдиармида, который можно получить у второго автора. онлайн-список публикаций.
Хотя алгоритм кучи в Floyd обладает лучшей производительностью в худшем случае и более узким внутренним циклом, вполне возможно, что алгоритм многократной вставки на самом деле быстрее (в среднем) для больших куч из-за эффектов кэша. См. Например, документ 1999 года «Анализ эффективности проектирования: строительство кучиДжеспер Боженс, Юрки Катаяйнен и Маз Спорк.
Замечания:
При проведении подобных экспериментов с использованием случайных данных важно избегать подсчета стоимости генерации случайных чисел. Для относительно быстрых алгоритмов, таких как вставка кучи, вполне возможно, что стоимость вызова PRNG значительна по сравнению со стоимостью алгоритма, в результате чего наблюдаемые результаты смещены линейной стоимостью генерации случайных чисел.
Чтобы избежать этого эффекта, вы должны предварительно сгенерировать случайный массив и затем измерить стоимость превращения его в кучу.
Как часто отмечалось, O (log N) является O (1) для всех практических значений N; если то, что у вас есть с1O (1) + с2O (журнал N) где с1 намного больше, чем с2, результат будет очень похож на O (1).
Другие решения
Возможно, что nlog (n) довольно близко к линейному для малых n.
Вы не могу скажи это не O(nlog(n))
- Первый график показывает меры
f(n), Это неверно, потому что
log(100000)все еще довольно мало по сравнению со значениями, показанными в
ось у, как6e+6, - Второй график показывает меры
f(n)/n, Это приемлемая мера, потому что она показывает поведение компонента логарифма. Но пока неясно, какlog2(10000) = 13.9а такжеlog2(125000) = 16.9, Которые дают соотношение 1,2 между двумя значениями. Только вашими глазами может быть неясно, исходит ли это от логарифма или другого мультипликатора.
Что нужно сделать дальше, чтобы было понятно:
- увеличить максимальное значение
n - Показывать только те точки данных, которые экспоненциально растут, т.е.
{2^0, 2^1,...,2^p,..., 2^n}, Вы ожидаете получить прямую линию, не параллельную оси X, чтобы решить, что она логарифмическая.
Я полагаю, что ничто из вашего исходного поста не позволит вам решить, что это не nlog(n)
если ты график ожидаемого времени работы, деленного на n, вы увидите сюжет, очень похожий на ваш второй сюжет aheap, Обратите внимание, что чем больше n становится, чем меньше становится наклон (как и ожидалось), так что это действительно выглядит как сходящееся к константе, а на самом деле это не так. Так что я думаю, что вы действительно наблюдаете O(n log n) время работы, только log n На больших значениях часть не сильно меняется, поэтому она выглядит как прямая линия.
На самом деле, ваш сюжет для aheap выглядит как прямая линия только от 25000 до 125000. Однако log(n) изменения в этом диапазоне только на 16% (ln(125000)/ln(25000)=1.1589...). Вы можете не заметить это изменение.