Временная сложность выполнения o (h) алгоритма n раз

Question

Какова временная сложность выполнения алгоритма O (h), когда h - это высота узла в BST n раз (число элементов в дереве), я считаю, что это O (n), а не O (n *) з) но я понятия не имею, как это доказать.

Алгоритм спецификации c, который работает в O (h), находит предшественника по порядку для элемента в BST.

Answer 1

Стоимость вычисления преемников по порядку n раз в любом BST составляет O (n). Чтобы увидеть это, посчитайте, сколько раз вы касаетесь каждого края дерева. Вы пройдете по краю один раз, когда впервые исследуете поддерево, и еще раз после того, как покинете его. В целом, это означает, что вы касаетесь каждого края не более двух раз, поэтому общая выполненная работа составляет O (n).

Обратите внимание, что, вообще говоря, вы можете ограничить стоимость выполнения n O (h) -времени на BST, который имеет высоту h в точке O (hn) и который никогда не будет недооценивать вещи. Однако, если вы знаете более конкретно о алгоритме, который вы используете, как в этом случае, вы можете получить более жесткий предел.

Answer 2

O (n²) .

Двоичное дерево поиска не сбалансировано, что означает, что высота узла может быть равна количеству узлов дерева, следовательно, O (n²).