Какова временная сложность вставки k новых элементов в двоичную кучу, содержащую уже n элементов? У меня есть ограничение, что мне нужно вставить k элементов в 0 (k + Log n) сложности.
Подсказка: используйте восходящий подход, аналогичный тому, который используется для построения кучи.
На этот вопрос нет простого ответа.
Вставка двоичной кучи будет иметь среднюю сложность O(1) и в худшем случае O(log N). Сложность останется в пределах этой границы независимо от k, но фактическое время, необходимое для завершения операции (не временная сложность; я полагаю, вы можете путать термины), будет зависеть от реализации, платформы и направления ветра.
Ближе к конкретному ответу с точки зрения времени является то, что время, необходимое для вставки k элементов, в лучшем случае будет линейно пропорционально k, а в худшем случае пропорционально log (x), интегрированному от N до k+N. Для N, значительно превышающего k, мы можем аппроксимировать время, затрачиваемое на пропорционально k log N.
Для получения дополнительной информации см.: http://en.wikipedia.org/wiki/Binary_heap.
k log (N) пропорционально времени, затраченному на первую вставку, умноженному на k, это хорошее приближение для k ‹‹ N, которое не указывается в OP. Фактическая сумма будет пропорциональна log N для первой вставки, log (N+1) для второй, и так до тех пор, пока мы не дойдем до log (N+k). Таким образом, общее затраченное время равно интегралу по этому диапазону, умноженному на k.
- person quant; 08.05.2014
O(1)? Похоже, это наилучший случай. Худший случай действительно O(log n).
- person Jim Mischel; 08.05.2014
