渐近时间复杂度、Big oh 和 Theta 分析。这是一个技巧问题吗？
Asymptotic time complexity, Big oh and Theta analysis. Is this a trick question though
问题如下：
考虑如下排序算法： I. 将给定输入A[1], A[2], ..., A[n]按给定顺序插入二叉搜索树T，从空开始树;二。对 T 进行中序遍历，以非降序输出元素。 (a) 该算法的最坏情况时间是多少？ (b) 该算法的最佳案例时间是多少？
我的回答：
我在 t(n) = 2(n/2) + n 中创建了一个 BST，因为我们必须遍历每个单独的元素，然后我还在 t(n) = 2(n/2) + n 中按顺序打印出 BST，因为我们必须再次遍历每个元素。然后我将时间复杂度加在一起，以 t(n) = 4(n/2)+2n.
结尾
按照师父的方法，符合情况一，制作θ(n^2)。如果是 θ(n^2)，这就回答了问题的 a 和 b。我看不出怎么会有更好的表现，或者在那种情况下表现更差。
这是一个技巧问题吗？
简答:
You added the RHS of the two equations but not the LHS – it should be 2T(n).
当然，T(n)的口头描述是"time complexity function"，但是什么？在这种情况下，它的时间复杂度应该是 或者 BST 创建 或者 中序遍历，而不是两者一起。
所以最后的结果是2T(n) = 4T(n/2) + 2n。取消 2，得到 O(n log n).
tl;博士回答:
But wait, why n log n for traversal too? There are only n elements, right?
通过将问题分成相等的两半 T(n/2)，您隐含地假设树在每次插入后都是 平衡的。对于简单的非自平衡 BST 树实现，情况并非总是如此。如果树的一侧是 "tilted"，则插入可能与 O(n) 一样多（即 O(n^2) 构造）。
幸运的是，对于大多数常用的自平衡树类型，例如Red-Black 和 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) 工作。
问题如下：
考虑如下排序算法： I. 将给定输入A[1], A[2], ..., A[n]按给定顺序插入二叉搜索树T，从空开始树;二。对 T 进行中序遍历，以非降序输出元素。 (a) 该算法的最坏情况时间是多少？ (b) 该算法的最佳案例时间是多少？
我的回答：
我在 t(n) = 2(n/2) + n 中创建了一个 BST，因为我们必须遍历每个单独的元素，然后我还在 t(n) = 2(n/2) + n 中按顺序打印出 BST，因为我们必须再次遍历每个元素。然后我将时间复杂度加在一起，以 t(n) = 4(n/2)+2n.
按照师父的方法，符合情况一，制作θ(n^2)。如果是 θ(n^2)，这就回答了问题的 a 和 b。我看不出怎么会有更好的表现，或者在那种情况下表现更差。
这是一个技巧问题吗？
简答:
You added the RHS of the two equations but not the LHS – it should be
2T(n).
当然，T(n)的口头描述是"time complexity function"，但是什么？在这种情况下，它的时间复杂度应该是 或者 BST 创建 或者 中序遍历，而不是两者一起。
所以最后的结果是2T(n) = 4T(n/2) + 2n。取消 2，得到 O(n log n).
tl;博士回答:
But wait, why
n log nfor traversal too? There are onlynelements, right?
通过将问题分成相等的两半 T(n/2)，您隐含地假设树在每次插入后都是 平衡的。对于简单的非自平衡 BST 树实现，情况并非总是如此。如果树的一侧是 "tilted"，则插入可能与 O(n) 一样多（即 O(n^2) 构造）。
幸运的是，对于大多数常用的自平衡树类型，例如Red-Black 和 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) 工作。