Почему мои бинарные вставки кучи ведут себя таким образом на практике?

Я реализовал в 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)?

4 4
c++ algorithm heap asymptotic-complexity

4 ответа:

Действительно верно, чтоожидаемое Время для построения двоичной кучи из случайных данных путем повторной вставки равно O(n), хотя наихудшее время (когда входные данные отсортированы) равно O(n log n). Этот интересный результат был известен в течение некоторого времени, хотя он, по-видимому, не является широко известным, предположительно из-за популярности известного гарантированного линейно-временного алгоритма heapify благодаря R. W. Floyd.

Интуитивно можно было бы ожидать среднего времени вставки для случайных элементов быть O (1), основываясь на предположении, что случайно построенная куча аппроксимирует полное бинарное дерево. Алгоритм вставки состоит в размещении элемента в конце кучи и последующем продвижении его путем многократного обмена с родительским элементом до тех пор, пока не будет выполнено ограничение кучи.

Если бы куча была полным бинарным деревом, среднее время вставки было бы действительно на O (1), так как в каждой точке цепочки свопов вероятность того, что потребуется еще один своп, была бы равна 0,5. Таким образом, в половине случаев своп не требуется; в четверти случаев требуется один своп, в восьмой-два свопа и т. д. Следовательно, ожидаемое число свопов равно 0 + 0.5 + 0.25 + ... = = 1.

Поскольку куча-это всего лишь аппроксимация полного бинарного дерева, приведенный выше анализ недостаточен. Невозможно поддерживать бинарное дерево без ребалансировки, которая имеет нетривиальную стоимость. Но вы можете продемонстрировать, что куча достаточно похожа на двоичный файл дерево, в котором ожидаемое время вставки по-прежнему равно O(1). Доказательство нетривиально; один анализ, доступный онлайн, - это "анализ среднего случая построения кучи путем повторной вставки" (1991) Райана Хейварда и Колина Макдиармида, который доступен из списка публикаций второго автора в интернете.

В то время как алгоритм Флойда heapify имеет лучшую производительность в худшем случае и более плотный внутренний цикл, возможно, что алгоритм повторной вставки на самом деле быстрее (в среднем) для больших кучи из-за эффектов кэша. См., например, статью Йеспера Бойесена, Юрки Катаяйнена и МАЗа Спорка 1999 года "пример проектирования производительности: кучное строительство".

Примечание:

При проведении подобных экспериментов с использованием случайных данных важно избегать подсчета стоимости генерации случайных чисел. Для относительно быстрых алгоритмов, таких как вставка кучи, вполне возможно, что стоимость вызова PRNG является значительной по сравнению со стоимостью алгоритма, вследствие чего наблюдаемые результаты искажаются линейной стоимостью генерации случайных чисел.

Чтобы избежать этого эффекта, необходимо предварительно сгенерировать случайный массив и затем измерить стоимость его преобразования в кучу.

Как часто отмечалось, O (log n ) - Это O (1) для всех практических значений n ; Если то, что вы имеете, является c1O (1) + c2O (log n) где c1 намного больше чем c2, результат будет очень похож на O(1).

1

Возможно, что nlog (n) довольно близок к линейному для малого n.

O (N log N) сложность - аналогична линейной?

0

Вы не можете сказать, что это не O(nlog(n))

    Первый график показывает меры f(n). Это неверно, потому что log(100000) все еще довольно мало по сравнению со значениями, показанными в ось y, как 6e+6.
  • второй график показывает меры f(n)/n. Это приемлемая мера, поскольку она показывает поведение логарифмической составляющей. Но пока неясно, как log2(10000) = 13.9 и log2(125000) = 16.9. Которые дают отношение 1,2 между двумя значениями. С вашими глазами только это может не ясно, если это происходит от логарифма или от другого мультипликатора.

Что вам нужно сделать дальше, чтобы быть ясным:

  1. увеличьте максимальное значение n
  2. показывают только точки данных, которые экспоненциально увеличиваются, т. е. {2^0, 2^1,...,2^p,..., 2^n}. Вы будете ожидать, что получите прямую линию, не параллельную оси x, чтобы решить, что она логарифмическая.

Мое мнение таково, что ничто на вашем первоначальном посту не позволяет вам решить, что это не nlog(n)

0

Если Вы построите график ожидаемого времени выполнения, разделенного на n, вы увидите сюжет, очень похожий на ваш второй сюжет aheap. Обратите внимание, что чем больше n становится, тем меньше становится наклон (как и ожидалось), поэтому он действительно выглядит как сходящийся к константе, в то время как на самом деле это не так. Поэтому я думаю, что то, что вы наблюдаете, действительно является O(n log n) временем выполнения, только часть log n не сильно меняется на больших значениях, поэтому она ложно выглядит как прямая линия.

На самом деле, ваш сюжет для aheap выглядит как прямая линия только начиная с 25000 до 125000. Однако log(n) изменяется в этом диапазоне только на 16% (ln(125000)/ln(25000)=1.1589...). Вы можете не заметить этого изменения.

0