Асимптотическая сложность времени, анализ Биг о и Тета.Это вопрос с подвохом, хотя

Question

Вот вопрос:

Рассмотрим следующий алгоритм сортировки: I. Вставьте заданный ввод A [1], A [2], ..., A [n] в двоичное дерево поиска T взаданный порядок, начиная с пустого дерева;II.Выполните обход по порядку T для вывода элементов в неубывающем порядке.а) Какое время наихудшего случая для алгоритма?(б) Какое время лучше всего подходит для алгоритма?

Мой ответ:

Я создал BST в t(n) = 2(n/2) + n, так как мы должны пройти через каждый отдельный элемент, я также затем напечатализ BST-порядка в t(n) = 2(n/2) + n, так как мы снова должны пройти через каждый элемент.Затем я добавил сложность времени, заканчивающуюся на t(n) = 4(n/2)+2n.

В соответствии с методом Учителя это соответствует случаю 1. Делая его θ(n^2).Если это θ(n^2), это отвечает и на a, и на b вопроса.Я не понимаю, как может быть лучшая производительность или в этом случае худшая производительность.

Это вопрос с подвохом?

Answer 1

Краткий ответ :

Вы добавили RHS двух уравнений, но не LHS - это должно быть 2T(n).

Конечно, словесное описание T(n) - это «функция сложности времени», но что ?В этом случае это должна быть временная сложность или создания BST или обхода по порядку, а не обоих вместе.

Таким образом, конечный результат равен 2T(n) = 4T(n/2) + 2n.Отмените 2, и вы получите O(n log n).

---

tl; dr answer :

Но подождите, почему n log n для обхода тоже?Есть только n элементов, верно?

Разбивая задачу на две равные половины T(n/2), вы неявно предполагаете, что дерево сбалансировано после каждой вставки.Для простой несбалансированной реализации дерева BST это не всегда так.Если дерево «наклонено» в одну сторону, вставка может составлять до O(n) (т. Е. O(n^2) конструкция).

К счастью, для наиболее часто используемых типов самобалансирующегося дерева, например, Red-Черный и AVL, вставка гарантированно будет O(log n) или ниже.Следовательно, правильное рекуррентное отношение для построения дерева равно T(n) = T(n - 1) + log n, которое получается равным O(n log n) (уравнение Стерлинга).

Тем не менее, обход для any BSTСбалансированный или нет, это O(n), так как есть только n элементов.Это означает, что ваше рекуррентное отношение для обхода неверно - оно должно быть T(n) = 2T(n/2) + 1, поскольку для каждого узла выполняется только O(1).