不同情况下数组与二分查找

Question

我一直在寻找二叉搜索树与数组并且很好奇我的假设是否正确。所以我会解释一下我的理解，如果你这么认为，请纠正我。我们还假设我们想要创建一个数据结构，它可以：

1. 给我们集合中最大/最小的元素
2. 查找集合中是否存在特定元素。

这是我的时间复杂度。

// If you go with array and:
//   not sort it per each insert: then 
//      -- lookup:
//           biggest/smallest - O(n)
//           specific element - O(n)
//      -- insert O(1)
//   sort it per each insert: then
//      -- lookup: 
//           biggest/smallest - O(1)
//           specific element - O(log(n)) (using binary search)
//      -- insert: O(nlog(n))          
// If you go with binary search tree:
//           biggest/smallest - O(log(n))
//           specific element - O(log(n))
//      -- insert log(n)

问题1：我想知道我的时间复杂度写得是否正确。想法？

问题2：事实证明我最喜欢第二个（排序数组）和第三个（二分搜索）选项。不过，唯一的区别是，对于数组，插入会更耗时

n

。除此之外，甚至可以在 O(1) 时间内找到特定元素，并且找到最大/最小元素。排序数组的插入时间是我们决定使用二叉搜索树的原因吗？ O(nlog(n)) 真的对我们有影响吗，所以我们改用 O(log(n)) 的二叉搜索树？

Answer 1

你的时间复杂度几乎是正确的，但是排序数组的插入操作有一个小错误。

当你向有序数组中插入一个元素时，你首先需要找到正确的插入位置，这需要 O(logn) 时间（使用二分查找），然后你可能需要移动剩余的元素，这需要 O( n) 时间。

因此在排序数组中插入操作的总时间复杂度是 O(n) 而不是 O(nlogn)