1
Что будет худшей временной сложностью для построения двоичного дерева поиска с заданными произвольными элементами N?Строит BST с N заданными элементами O (n lg n)?
Я думаю, что есть разница между N заданных элементов и элементов, поступающих один за другим и, тем самым делая BST от общего числа N элементов.
В первом случае, это О (п § п) и во втором является O (N^2). Я прав ?
Что нового в том, чтобы принимать элементы по одному, а затем разобраться со всем этим сразу? – dasblinkenlight
Я думаю, что более поздний случай может построить Skewed BST, тем самым имея O (n^2) – Garrick
Принимая числа один за другим, O (n) во времени и O (n) в пространстве. Теперь вы можете отсортировать их и построить идеальное дерево в O (n * log n). Если вы должны построить дерево по ходу (т. Е. Нет дополнительного пространства O (n) для ввода доступно), то вы можете получить несимметричное дерево для O (n^2) наихудшего случая. – dasblinkenlight