Как построение кучи может быть O (n) сложностью по времени?

Question

Может кто-нибудь помочь объяснить, как сборка кучи может быть O (n) сложностью?

Вставка элемента в кучу - O(log n), и вставка повторяется n / 2 раза (остальные - листья, и они не могут нарушать свойство кучи).Таким образом, это означает, что сложность должна составлять O(n log n), я бы подумал.

Другими словами, для каждого элемента, который мы «heapify», он может быть отфильтрован один раз для каждого уровня кучи.до сих пор (то есть log n уровней).

Чего мне не хватает?

Answer 1

В основном, работа выполняется только на неконечных узлах при построении кучи ... и проделанная работа - это объем обмена, чтобы удовлетворить условию кучи ... другими словами (в худшем случае) это количество пропорционально на высоту узла ... в целом сложность задачи пропорциональна сумме высот всех неконечных узлов .. которая равна (2 ^ h + 1 - 1) -h-1 = nh -1 = O (n)

Answer 2

Последовательные вставки могут быть описаны следующим образом:

T = O(log(1) + log(2) + .. + log(n)) = O(log(n!))

Путем аппроксимации по скворецу n! =~ O(n^(n + O(1))), поэтому T =~ O(nlog(n))

Надеюсь, это поможет, оптимальный способ O(n) используеталгоритм построения кучи для заданного набора (порядок не имеет значения).

Answer 3

Предположим, у вас есть N элементов в куче. Тогда его высота будет Log (N)

Теперь вы хотите вставить другой элемент, тогда сложность будет такой: Log (N) , мы должны сравнить все пути UP с корнем.

Теперь у вас есть N + 1 элементов и высота = Журнал (N + 1)

Используя метод индукция , можно доказать, что сложность вставки будет gilogi .

Сейчас используется

log a + log b = log ab

Это упрощает до: ∑logi = log (n!)

что на самом деле O (NlogN) * ​​1038 *

Но

мы здесь что-то не так делаем, так как во всех случаях мы не достигаем вершины. Следовательно, выполняя большую часть времени, мы можем обнаружить, что мы не идем даже на полпути вверх по дереву. Таким образом, эту границу можно оптимизировать, чтобы получить другую более жесткую границу с помощью математики, приведенной в ответах выше.

Это осознание пришло ко мне после детализации и экспериментов на кучах.

Answer 4

"Линейная временная граница сборки Heap, может быть показана путем вычисления суммы высот всех узлов в куче, которая является максимальным количеством пунктирных линий. Для идеального бинарного дерева высотой h, содержащего N = 2 ^ (h + 1) - 1 узлов, сумма высот узлов равна N - H - 1. Таким образом, это O (N). "

Answer 5

Мне действительно нравится объяснение Джереми Уэста .... здесь представлен еще один подход, который очень легко понять http://courses.washington.edu/css343/zander/NotesProbs/heapcomplexity

, поскольку сборка heep зависит от использования heapify и используется подход смещениякоторый зависит от суммы высот всех узлов.Итак, чтобы найти сумму высоты узлов, которая определяется как S = суммирование от i = 0 до i = h (2 ^ i * (hi)), где h = logn - высота дерева, решающего s, мы получаемs = 2 ^ (h + 1) - 1 - (h + 1), поскольку n = 2 ^ (h + 1) - 1 s = n - h - 1 = n-logn - 1 s = O (n),и поэтому сложность buildheap составляет O (n).

Answer 6

думаю, что вы делаете ошибку. Взгляните на это: http://golang.org/pkg/container/heap/ Создание кучи - это не O (n). Однако вставка - это O (lg (n). Я предполагаю, что инициализация - это O (n), если вы устанавливаете размер кучи b ​​/ c, то куча должна выделять пространство и настраивать структуру данных. Если у вас есть n элементов для размещения в куче, тогда да, каждая вставка - это lg (n), а n элементов - n, поэтому вы получите n * lg (n), как указано выше