В нотации Big-O для древовидных структур: почему некоторые источники ссылаются на O (logN), а некоторые на O (h)?

Question

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

Версия # 1: алгоритм обхода в худшем случае сравнивается один раз на высоту дерева;следовательно, сложность равна O(h).

Версия # 2: алгоритм обхода в худшем случае сравнивается один раз на высоту дерева;поэтому сложность составляет O(logN).

Мне кажется, что работает одна и та же логика, но разные авторы используют либо logN, либо h.Может кто-нибудь объяснить мне, почему это так?

Answer 1

Правильным значением времени поиска в наихудшем случае для дерева является O (h), где h - высота дерева.Если вы используете сбалансированное дерево поиска (в котором высота дерева равна O (log n)), то время поиска - наихудший O (log n).Тем не менее, не все деревья сбалансированы.Например, вот дерево с высотой n - 1:

1
 \
  2
   \
    3
     \
     ...
       \
        n

Здесь h = O (n), поэтому поиск - O (n).Правильно сказать, что время поиска также равно O (h), но h ≠ O (log n) в этом случае, и было бы ошибочным утверждать, что время поиска было O (log n).

Короче говоря, O (h) - правильная оценка.O (log n) - это правильная граница в сбалансированном дереве поиска, когда высота не превышает O (log n), но не все деревья имеют время поиска O (log n), поскольку они могут быть несбалансированными.

Надеюсь, это поможет!

Answer 2

Если ваше двоичное дерево сбалансировано так, что у каждого узла есть ровно два дочерних узла, тогда число узлов в дереве будет точно N = 2 ^h - 1, поэтому высота - это логарифм количества элементов (и аналогично для любого полного n -ного дерева).

Произвольное, неограниченное дерево может выглядеть совершенно иначе,хоть;например, он может иметь только один узел на каждом уровне, поэтому N = h в этом случае.Таким образом, высота является более общей мерой, поскольку она относится к фактическим сравнениям, но при дополнительном допущении баланса вы можете выразить высоту как логарифм числа элементов.

Answer 3

O (h) относится к двоичному дереву, которое отсортировано, но не сбалансировано

O (logn) будет относиться к дереву, которое отсортировано и сбалансировано

Answer 4

Это два способа сказать одно и то же, потому что ваше среднее сбалансированное двоичное дерево высоты 'h' будет иметь около 2 ^ узлов.

В зависимости от контекста высота или #nodesбыть более релевантным, и вот на что вы увидите ссылки.

Answer 5

потому что (h) восьмерка сбалансированного дерева изменяется как логарифм (N) числа элементов