Сложности обходов бинарных деревьев

Question

Какова временная сложность обхода по порядку, порядку и порядку бинарных деревьев в структурах данных ?? Это O (n) или O (log n) или O (n ^ 2) ??

Answer 1

Обходы в порядке, до и после заказа - это обходы в глубину.

Для графа сложность первого обхода глубины составляет O (n + m), где n - количество узлов, а m - количество ребер.

Поскольку бинарное дерево также является графом, то же самое применимо и здесь. Сложность каждого из этих обходов в глубину составляет O (n + m).

Поскольку количество ребер, которые могут исходить из узла, ограничено 2 в случае двоичного дерева, максимальное число общих ребер в двоичном дереве равно n-1, где n - общее количество узлов.

Тогда сложность становится O (n + n-1), то есть O (n).

Answer 2

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

Answer 3

O (n), я бы сказал. Я делаю для сбалансированного дерева, применимого для всех деревьев. Предполагая, что вы используете рекурсию,

T (n) = 2 * T (n / 2) + 1 ----------> (1)

T (n / 2) для левого поддерева и T (n / 2) для правого поддерева и '1' для проверки базового случая.

В Упрощении (1) вы можете доказать, что обход (либо по заказу, либо по предварительному заказу, либо по заказу) имеет порядок O (n).

Answer 4

Обход равен O (n) для любого ордера - потому что вы попадаете в каждый узел один раз. В режиме поиска оно может быть меньше O (n), ЕСЛИ дерево имеет какую-то организационную схему (т. Е. Дерево двоичного поиска).

Answer 5

Введение

Привет

Мне задали этот вопрос сегодня в классе, и это хороший вопрос!Я объясню здесь и надеюсь, что мой более официальный ответ будет рассмотрен или исправлен там, где он неправильный.:)

Предыдущие ответы

Наблюдение @Assaf также является правильным, поскольку обход двоичного дерева рекурсивно проходит один раз для посещения каждого узла.

Но !, поскольку он рекурсивныйАлгоритм, вам часто приходится использовать более продвинутые методы для анализа производительности во время выполнения.При работе с последовательным алгоритмом или алгоритмом, использующим циклы for, часто достаточно использовать суммирование.Итак, ниже приводится более подробное объяснение этого анализа для любопытных.

Повторение

Как уже говорилось ранее,

T (n) =2 * T (n / 2) + 1

, где T (n) - количество операций, выполненных в вашем алгоритме обхода (порядок, предварительный порядок или пост-порядок не имеют значения).

Объяснение повторения

Существует два T (n) , потому что обходы inorder, preorder и postorder все вызывают себя на левом и правом дочернем узле.Думайте о каждом рекурсивном вызове как T (n) . Другими словами, ** левый T (n / 2) + правый T (n / 2) = 2 T (n / 2) **«1» происходит от любых других операций с постоянным временем в функции, таких как печать значения узла и т. Д. (Честно говоря, это может быть 1 или любое постоянное число, и асимптотическое время выполнения все еще вычисляется в то же значение. Объяснениеследует.).

Анализ

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

T (n) = 2 * T (n / 2) + постоянная

где постоянная - некоторая постоянная (может быть 1или любая другая константа).

Используя теорему Мастера , мы имеем T (n) = a * T (n / b) + f (n) .

Итак, a = 2, b = 2, f (n) = константа , поскольку f (n) = n ^ c = 1 , то следуетчто c = 0 , поскольку f (n) является константой.

Отсюда мы можем видеть, что a = 2 и b ^ c = 2 ^ 0 = 1 .Итак, a> b ^ c или 2> 2 ^ 0 .Итак, c или 0

Отсюда мы имеем T (n) = BigTheta (n ^ {logb (a)}) = BigTheta (n ^ 1) = BigTheta (n)

Если вы не знакомы с BigTheta (n), это "похоже" (пожалуйста, потерпите меня :))до O (n) , но это "более жесткая граница" или более точное приближение времени выполнения.Итак, BigTheta (n) является наихудшим O (n) и лучшим BigOmega (n) во время выполнения.

Надеюсь, это поможет.Береги себя.

Answer 6

T (n) = 2T (n / 2) + c

T (n / 2) = 2T (n / 4) + c => T (n) = 4T (n / 4) + 2c + c

аналогично T (n) = 8T (n / 8) + 4c + 2c + c

....

....

последний шаг ... T (n) = nT (1) + c (сумма степеней от 2 до 0 (высота дерева))

, поэтому Сложность равна O (2 ^ (h + 1) -1)

но h = log (n)

Итак, O (2n - 1) = O (n)