Начиная с пустого дерева, какова сложность вставки в Red Black Tree в нотации big-O?

Question

Если у меня есть 10 элементов и, начиная с пустого дерева, какова сложность вставки 10 элементов в красный черный в нотации big-O?

Будет ли оно больше O (журнал 10), потому что каждый раз, когда он вставляет элемент, он должен искать подходящее место для элемента и выполнять серию вращений между узлами-предками и дочерними узлами. Так что, если у меня есть элемент N и вставка N раз в Red Black Tree, разве это не сделает его O (n log n)?

Спасибо за любую помощь.

Answer 1

Вы никогда не используете big-O с константой (кроме 1), потому что O (10) означает то же самое, что O (1) или O (128291), поэтому по соглашению вы всегда используете O (1)!

Итак, давайте посмотрим, что является большим плюсом при вставке K элементов в изначально пустое RB-дерево. Первая вставка - это постоянное время, поэтому назовите его O (1); и вставляя, когда есть X элементов, X + 1-й является O (log (X)) (даже если вам нужно повернуть каждый шаг вниз, он все равно в худшем случае пропорционален log (X), поэтому O (log (X) ), поскольку число «слоев» или «уровней» растет только логарифмически с X - поскольку дерево RB для уровней K имеет число узлов, которое увеличивается как 2 до степени K).

Итак, мы хотим суммировать log (X) для X от 2 до N (плюс стоимость), который равен логарифму факториала N. Per Приблизительно Стирлинга, это о N log (N) - N, который в терминах биг-О снова сводится к N log (N).

Answer 2

На самом деле @Justice и @Alex получают то, что показатель сложности O(f(N)) говорит об ограничивающем поведении (например, время выполнения, количество сравнений и т. Д.), Когда N стремится к бесконечности.

Они говорят, что если вы замените определенное значение на N, терминология O больше не будет иметь смысла.

Есть еще один момент, который они не сделали. Это означает, что вы не можете использовать оператор в нотации O(...), чтобы сказать вам, что происходит, когда N мало. По определению нотация «большой О» ничего не говорит вам о том, что происходит в этом случае.

Это не просто педантизм. Например, функция стоимости F(N) = 1,000,000 * N + N**2 равна O(N**2), но первый член доминирует для значений N, меньших 1000. Если вы попытаетесь использовать меру O(N**2) в качестве оценщика в этом случае, вы получите совершенно неправильный ответ.

Answer 3

Временная сложность вставки одного элемента в дерево RB составляет O(log n), где n - текущий размер дерева.

Сложность времени вставки элементов n в пустое дерево RB, следовательно, составляет O(n log n).

Сложность по времени вставки 10 элементов в пустое дерево RB постоянна, или O(1). Поскольку дерево начинается пустым, а количество вставляемых элементов фиксировано, здесь нет переменных элементов.