Я реализую 2-3-4 дерева для управления каким-то образом. Во время инициализации моего приложения я хочу вставить туда некоторое количество целых чисел (получить его как ввод - n) Что такое сложность такой вставки? O (nloglog (n))?Вставка в 2-3-4 дерева количество узлов
Сложность вставки на дереве 2-3-4 равна O (log (n)).
Мы можем видеть квоту от Wikipedia
2-3-4 деревьев В-дерева порядка 4 (1998 г.) Кнут
Сложность вставки на B-дерева вывода (log (n)), так же как и дерево 2-3-4. Повторяя вставку для инициализации дерева 2-3-4, можно сказать, что стоимость времени init - это O (n * log (n)). Но мы можем ожидать, особый способ построения [link]:
В приложениях часто бывает полезно построить B-дерева, чтобы представлять большой существующий сбор данных, а затем обновить его пошагово с использованием стандартного B-дерева операции. В этом случае наиболее эффективным способом построения исходного B-дерева является не вставлять каждый элемент в исходный набор последовательно, а вместо этого строить исходный набор листовых узлов непосредственно из ввода, а затем строить из них внутренние узлы. Такой подход к построению B-дерева называется насыпной загрузкой. Первоначально каждый лист, но последний имеет один дополнительный элемент, который будет использоваться для построения внутренних узлов.
Стоимость времени может быть (n + n/4 + n/16 + ... + n/(4^h)). На основе суммы геометрической прогрессии. Я рассчитываю стоимость времени. Он меньше (4/3) * n.
Просьба указать, есть ли у меня ошибка при расчете.
Вы спрашиваете * как читать аргументы, переданные моему приложению *? Твой вопрос очень трудно понять. –
@Allendar - я задаю вопрос о сложности приложения init - i.d, вставляя по-одному n элементов в дерево 2-3-4 – Yakov