При изучении сложности любого алгоритма, который пересекает двоичное дерево поиска, я вижу два разных способа выразить одно и то же:
Версия №1: алгоритм обхода в худшем случае сравнивается один раз за высоту дерева; поэтому сложность O(h)
.
Версия №2: алгоритм обхода в худшем случае сравнивается один раз за высоту дерева; поэтому сложность O(logN)
.
Мне кажется, что та же логика работает, но разные авторы используют либо logN
, либо h
. Может кто-нибудь объяснить мне, почему это так?