data-structures - 不同数据结构的大 O 运行时间

Question

我试图提出以下数据结构的大 O 运行时间。 他们正确吗？

• 将 n 个整数插入到最初为空的 AVL 树中(最佳情况) O(log n)

• 将 n 个整数插入到最初为空的 AVL 树中(最坏情况) O(log n)

• 将 n 个整数插入初始为空的二叉搜索树中，该二叉搜索树不强制执行 结构特性(最佳情况) O(log n)

• 将 n 个整数插入初始为空的二叉搜索树中，该二叉搜索树不强制执行 结构特性(最坏情况) O(n)

解释为什么它们不正确也会很有帮助

Answer 1

我在这里假设您需要插入所有元素的总时间:

(1) 在 AVL 树的最佳情况，您将永远不需要低于根，[即所有元素都等于根]，所以它将是 O(n)。 [无论树的大小如何，都不需要加深超过 1 步]。每个元素 O(1)。

(2) AVL 树的最坏情况:向 AVL 树插入 n 个整数是 O(nlogn)。每一步都是 O(log(T))，其中 T 是当时的大小。 O(log1) + O (log2) + ... + O(logn) = O(log1 + log2 + ... + logn) = O(log(1*...*n)) = O (nlogn)。所以 O(nlogn)。每个元素 O(logn)

(3) 没有强制执行结构，最好的情况，仍然是 O(n)，与 (1) 的原因相同。在最好的情况下，你添加的所有元素都是根，所以你永远不需要在树中向下走，不管它的大小是多少。每个元素 O(1)。

(4) 没有强制执行结构，最坏的情况:正如其他答案中所说，找到每个元素的位置是 O(n)，所以总的来说，你的时间复杂度最差O(n^2)。每个元素 O(n)。