大O运行时间为不同的数据结构
我试图想出以下数据结构的大O运行时间。 他们是否正确？
将n个整数插入最初为空的AVL树（最佳情况） O（log n）
将n个整数插入最初为空的AVL树（最坏情况） O（log n）
将n个整数插入不执行结构属性的最初空的二叉搜索树（最佳情况） O（log n）
将n个整数插入最初为空的二叉搜索树中，该搜索树不强制执行结构属性（最坏情况） O（n）
另外一个解释，为什么他们不正确将是有益的
这在你的定义中是不正确的：
将n个整数插入最初为空的AVL树（最佳情况）O（log n）
你不能在少于n操作中访问（和复制） n数据项，因为你应该读每个项目（所以， O(n)仅仅是在n个元素上移动的最小值）。
所以，我的假设是，你给了单个元素的正确的O() （这有点不对，因为最好的可以通过特殊的输入来实现;你的估计是平均情况，而不是最好的），所以，将每个乘以O(n) ：
将n个整数插入最初为空的AVL树（最好的情况） O(n*log n) UPDATE：这是平均值; 特殊输入的最佳时间可以减少。
将n个整数插入最初为空的AVL树（最坏情况） O(n*log n)
将n个整数插入最初为空的二叉搜索树中，该树不强制结构属性（最好的情况） O(n*log n) UPDATE ：这可能取决于实现和整数序列; 所以最好的情况是O(n) （见评论）。
将n个整数插入不执行结构属性（最坏情况）的最初为空的二叉搜索树O(n*n)
我假设你需要总共插入所有元素的时间：
（1） 对于AVL树来说 ， 最好的情况是 ，你永远不需要去根的下面，[即所有的元素都等于根]，所以它将是O（n） 。 [无论树的大小如何，永远不需要加深多一步]。 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）每个元素。
如何插入n整数产生O(logn)的大O. 这没有任何意义。 当然， 阅读整数本身至少需要O(n) 。
所以对于不平衡的，BST例子最坏的情况是你插入一个像1,2,3,4这样的数字排序列表。 插入1需要0次。 插入2需要~1次。 插入3需要~2次。 等等。这相当于1+2+3+...+n = O(n^2) 。
同样在最好的情况下，每个后续插入都需要log(i)时间。 所以总运行时间是log(1)+log(2)+log(3)+...+log(n) 。 这个评估的结果并不是很明显。 但是如果你知道一点微积分，你可以看到这是（几乎）梯形法则近似log n从1到n的积分。 这大约是nlogn - n = O(nlogn) 。
我相信你可以对AVL树进行类似的分析。
链接地址: http://www.djcxy.com/p/40013.html