1
Рассмотрите временную сложность обхода после заказа на двоичном дереве поиска N узлов. Я знаю, что требуется O(N) для посещения всех узлов, в общем случае, но какова сложность в худшем случае, когда BST - это список? Я думаю, что он принимает O(N^2), потому что он пройдет через N узлов, чтобы добраться до конца, и N узлов, чтобы вернуться к началу. Это значит N*N = N^2, поэтому я думаю, что это O(N^2). Это правильно?Худшая временная сложность BST (перемещение по расписанию)
Возможно, вам стоит рассмотреть возможность добавления примера того, что вы понимаете как * обход * в BST. Как уже было сказано, вы посещаете все узлы и возвращаетесь назад, что приводит к выполнению шагов «n + n» или «O (n)» по сложности. Обратите внимание, что это опустошает значение * худшего *, поскольку единственный случай, который у вас есть, - это когда вы проходите все узлы и обратно. (Что хуже, чем здесь?) – Rubens