Относительно новый для алгоритмов, поэтому, пожалуйста, прости, если я пропустил что-то очевидное!
Я знаю, что сложность поиска в глубину обычно выражается как O (h), где h - этовысота дерева, тогда как сложность поиска в ширину равна O (n), где n - количество узлов в дереве.
Я понимаю объяснение (например, в этом ответе https://stackoverflow.com/a/9844323/10083571), что в худшем случае в BFS все узлы находятся на одном уровне, что означает, что мы должны поставить все узлы в очередь, прежде чем переходитьЯ также понимаю, что сложность дерева в пространстве будет определяться его высотой, так как это будет определять максимальные слои в стеке, которые необходимо будет сохранить.
То, чего я не понимаюпочему это также не выражается как O (n). Наряду с рассуждением, аналогичным наихудшему случаю BFS, не является ли наихудший случай DFS, что все узлы расположены друг над другом, вдоль одной линии? Так в худшем случае,высота дерева будет равна числу узлов, которые у него есть. Так почему же это не выражается как O (n)?
Спасибо