В нотации Big-O для древовидных структур: почему некоторые источники ссылаются на O (logN), а некоторые - на O (h)?
При изучении сложности любого алгоритма, который пересекает двоичное дерево поиска, я вижу два разных способа выразить одно и то же:
Версия №1: алгоритм обхода в худшем случае сравнивается один раз за высоту дерева; поэтому сложность O(h).
Версия №2: алгоритм обхода в худшем случае сравнивается один раз за высоту дерева; поэтому сложность O(logN).
Мне кажется, что та же логика работает, но разные авторы используют либо logN, либо h. Может кто-нибудь объяснить мне, почему это так?
Ответы
Ответ 1
Если ваше двоичное дерево сбалансировано, так что каждый node имеет ровно два дочерних узла, то число узлов в дереве будет равно N = 2 h & minus; 1, поэтому высота является логарифмом числа элементов (и аналогично для любого полного n-арного дерева).
Произвольное, безусловное дерево может выглядеть совершенно другим; например, он может иметь только один node на каждом уровне, поэтому N = h в этом случае. Таким образом, высота является более общей мерой, поскольку она связана с фактическими сравнениями, но при дополнительном допущении баланса вы можете выразить высоту как логарифм числа элементов.
Ответ 2
Правильное значение для наихудшего времени поиска - это дерево O (h), где h - высота дерева. Если вы используете сбалансированное дерево поиска (такое, где высота дерева O (log n)), то время поиска является наихудшим O (log n). Тем не менее, не все деревья сбалансированы. Например, здесь дерево с высотой n - 1:
1
\
2
\
3
\
...
\
n
Здесь h = O (n), поэтому поиск - O (n). Правильно сказать, что время поиска также равно O (h), но h & ne; O (log n) в этом случае, и было бы ошибочным утверждать, что время поиска было O (log n).
Короче говоря, O (h) - правильная оценка. O (log n) - правильная граница в сбалансированном дереве поиска, когда высота не превышает O (log n), но не все деревья имеют время поиска O (log n), потому что они могут быть несбалансированы.
Надеюсь, это поможет!
Ответ 3
O (h) будет ссылаться на двоичное дерево, которое сортируется, но не сбалансировано
O (logn) будет ссылаться на дерево, которое сортируется и сбалансировано
Ответ 4
Это два способа сказать одно и то же, потому что ваше среднее сбалансированное двоичное дерево с высотой "h" будет иметь около 2 ^ h узлов.
В зависимости от контекста высота или #nodes могут быть более релевантными, и так, что вы увидите ссылку.
Ответ 5
поскольку (h) восемь сбалансированного дерева изменяются как журнал (N) элементов элементов
