有人可以向我解释一下构建 BST 的最坏情况下的运行时间是 n^2 吗？我问了我的教授，我收到的唯一反馈是
“因为树与输入的大小成线性关系。成本是 1+2+3+4+...+(n-1)。”
有人可以用不同的方式解释吗？她的解释让我觉得它的 O(n)....
问问题
1009 次
3 回答
0
我猜 1+2+3+4+...+(n-1) 插入步骤很清楚，（对于反向排序列表）。
您应该对这个步数是二次方的想法感到满意。考虑运行算法两次并计算步数：
[1+2+3+4+...+(n-1)] + [1+2+3+4+...+(n-1)] = [1+2+3+4+. ..+(n-1)] + [(n-1) + ... + 4+3+2+1] = n+n+...n = n^2
因此，一次运行需要 0.5*n^2 步。
于 2013-10-08T16:00:44.847 回答
0
我认为最坏的情况发生在输入已经排序时：A、B、C、D、E、F、G、H。这就是为什么您可能希望在适用的情况下随机排列输入序列。
于 2013-10-08T00:57:00.107 回答
0
最坏情况下的运行时间与输入的平方成正比，因为 BST 是不平衡的。一个不平衡的 BST 可以表现出退化的结构：在最坏的情况下，一个单链表。构建此列表将要求每个插入沿着增长列表的全长行进，以到达叶节点以添加新叶。
例如，尝试对正好相反顺序的数据运行算法，这样每个新节点都必须成为树的新最左边节点。
只有当输入数据已经排序时，才能在线性时间内构建 BST（甚至是平衡的！）。此外，这是使用利用顺序的特殊算法完成的；不是通过执行 N 次插入。
于 2013-10-08T00:57:03.670 回答