从大小为 n 的整数的未排序数组构造二叉搜索树
Constructing a binary search tree from an unsorted array of size n of integers
我对此的思考过程是这个算法是不正确的。要从大小为 n 的整数的未排序数组创建二叉树，需要先对数组进行排序。我们知道任何基于比较的排序算法都有 omega(nlog(n)) 的下限运行时间，因为我们不能比它更好。
数组排序后，我们需要一种正确创建 BST 的方法。 （按顺序查看 keys/nodes 必须以 increasing/sorted 的方式）我们查看数组的中间元素并将其作为树的根。然后我们在数组的左半部分递归地执行此操作，构造左子树，并使其成为根的左子树。我们还在数组的右半部分递归地执行此操作，构造右子树，并使其成为根的右子树。由于递归关系，它的运行时间将为 O(n)：T(n) = 2T(n/2) + c。这是在我们上面的排序之后发生的，所以总运行时间是
O(nlog(n) + n) 就是 O(nlog(n))。这表明我们没有比这更好的方法了。
有什么我可以补充的吗？或者这就足够了吗？有人有其他 suggestions/thoughts 吗？谢谢。
您假设要创建二叉树，您需要首先对整数进行排序作为第一步。由于这是一个不合理的假设，您的证明无效。
为了正确证明结果，你需要假设你可以在nloglogn比较中创建BST，并由此证明矛盾。矛盾是直接的，因为从 BST 你可以在线性时间内得到一个排序的整数列表（从树的中序遍历），所以你会有一个 nloglogn 比较排序。
这个证明大概是出题人的本意，但我认为题的前提是错误的。正如您提出的那样，问题并未指定对给定整数的唯一操作是比较，因此 X 教授的算法可能使二叉搜索树的操作不是比较。那么就不会有矛盾，因为它可以用来对整数进行排序，但 而不是 是比较排序。例如，融合树可用于在少于 O(n log n) 次算术运算中对 n 个整数进行排序（参见 https://www.sciencedirect.com/science/article/pii/0022000093900404）。
我对此的思考过程是这个算法是不正确的。要从大小为 n 的整数的未排序数组创建二叉树，需要先对数组进行排序。我们知道任何基于比较的排序算法都有 omega(nlog(n)) 的下限运行时间，因为我们不能比它更好。
数组排序后，我们需要一种正确创建 BST 的方法。 （按顺序查看 keys/nodes 必须以 increasing/sorted 的方式）我们查看数组的中间元素并将其作为树的根。然后我们在数组的左半部分递归地执行此操作，构造左子树，并使其成为根的左子树。我们还在数组的右半部分递归地执行此操作，构造右子树，并使其成为根的右子树。由于递归关系，它的运行时间将为 O(n)：T(n) = 2T(n/2) + c。这是在我们上面的排序之后发生的，所以总运行时间是 O(nlog(n) + n) 就是 O(nlog(n))。这表明我们没有比这更好的方法了。
有什么我可以补充的吗？或者这就足够了吗？有人有其他 suggestions/thoughts 吗？谢谢。
您假设要创建二叉树，您需要首先对整数进行排序作为第一步。由于这是一个不合理的假设，您的证明无效。
为了正确证明结果，你需要假设你可以在nloglogn比较中创建BST，并由此证明矛盾。矛盾是直接的，因为从 BST 你可以在线性时间内得到一个排序的整数列表（从树的中序遍历），所以你会有一个 nloglogn 比较排序。
这个证明大概是出题人的本意，但我认为题的前提是错误的。正如您提出的那样，问题并未指定对给定整数的唯一操作是比较，因此 X 教授的算法可能使二叉搜索树的操作不是比较。那么就不会有矛盾，因为它可以用来对整数进行排序，但 而不是 是比较排序。例如，融合树可用于在少于 O(n log n) 次算术运算中对 n 个整数进行排序（参见 https://www.sciencedirect.com/science/article/pii/0022000093900404）。