Сложности прохождения двоичных деревьев

Ответ 1

По порядку, предзаказа и постобработкам проходят обходные пути.

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

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

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

Затем сложность становится O (n + n-1), которая является O (n).

Ответ 2

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

Ответ 3

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

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

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

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

Ответ 4

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

Ответ 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 <logb (a) или 0 <log2 (2)

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

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

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

Ответ 6

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

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 до h (высота дерева))

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

но h = log (n)

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