Чтобы построить кучу, часто ошибочно считают, что O (n log n) - это строгая верхняя граница, но на самом деле это O (n).
Я хочу сказать, что извлечение всех n элементов из кучи - это O (n log n), но, исходя из того, что я знаю о сложности построения кучи, я колеблюсь и думаю, что это может быть O (n) для по той же причине создание кучи - O (n).
Это верно?
Каждый раз, когда мы открываем, нам нужно найти новый корень, а функция heapify займет время O (h), где h - высота двоичного дерева. Для сбалансированного двоичного дерева, такого как куча, h = log_2 (n). Но количество узлов уменьшается один за другим для каждого попа, поэтому h должно уменьшаться.
Поэтому, если бы мне нужно было вычислить сложность, я бы сделал что-то вроде
O(log_2(n) + log_2(n-1) + ... + log_2(1))
= O(log_2(n * (n-1) * ... * (1))
= O(log_2(n^n))
= O(n log_2(n)
Но действительно ли это строгая верхняя граница?
