Когда мы говорим о временной или пространственной сложности, мы имеем в виду скорость, с которой меняются временные или пространственные требования относительно размера входных данных.Например.когда мы говорим O (1), мы имеем в виду, независимо от размера ввода, время (в случае сложности времени) или пространство (в случае сложности пространства) является постоянным.Таким образом, O (1) означает , а не означает 1 секунду или 1 минуту.Это просто означает постоянный по отношению к размеру ввода.Если вы построите график времени выполнения для разных входных размеров, вы получите горизонтальную линию.Аналогичное имеет место для O (n) или O (log n).
Теперь с этим пониманием, давайте поговорим о дереве AVL.Дерево AVL является сбалансированным бинарным деревом поиска.Поэтому средняя сложность времени для поиска узла в дереве составляет O (log n).Обратите внимание, что для поиска узла вы не посещаете каждый узел дерева (в отличие от LinkedList).Если бы вам приходилось посещать каждый отдельный узел, вы бы сказали, что временная сложность равна O (n).В случае дерева AVL, каждый раз, когда вы обнаруживаете несоответствие, вы отбрасываете одну половину дерева и переходите к поиску в оставшейся половине.
В худшем случае вы будете делать одно сравнение на каждом уровне дерева, т.е. равным высоте дерева, поэтому сложность времени поиска составляет O (log n).Размер левого дерева равен , а не O (log n).
Говоря о размере, вам нужно место для хранения каждого узла.если вам нужно хранить 1 узел, вам потребуется 1 единица пространства, для 2 узлов, 2 единицы, для 3 узлов, 3 единицы и так далее.Этот блок может быть что угодно 10 байт, 1 КБ, 5 КБ, что угодно.Дело в том, что если вы построите требование к пространству ввода в памяти компьютера по отношению к количеству деревьев, все, что вы получите, - это линейный график, начинающийся с нуля.Это O (n).
Слишком дальнейшее уточнение при вычислении временной или пространственной сложности алгоритма, если сложность получается как O (1 + log n + 4n + 2 ^ n + 100), мы вызываемэто O (2 ^ n), т. е. мы берем наибольшее значение, потому что мы не вычисляем абсолютное значение, мы рассчитываем скорость изменения по отношению к размеру ввода, и, следовательно, самое большое значение имеет значение.
Если вы говорите о временной сложности алгоритма для расчета размера дерева, вам необходимо посетить каждый узел дерева.Поскольку общее число узлов равно n, оно будет равно O (n).