每个项目是O(n),并且有n个项目.即使每个项目的O(n)是"随着它增加"n,你仍然得到0 + 1 + 2 + 3 ...(n-1),即n(n-1)/ 2 = O( N ^ 2).
换句话说,假设我们正在添加10,20,30,40:
第1步:空树,插入10:
10
第2步:比较20和10; 更大,因此树变成:
10
\
20
第3步:将30与10进行比较; 更大,所以向下移动到20节点.比较30与20; 更大,因此树变成:
10
\
20
\
30
第4步:将40与10进行比较; 更大,所以向下移动到20节点.将40与20进行比较; 更大,所以向下移动到节点30比较40与30; 更大,因此树变成:
10
\
20
\
30
\
40
注意我们每次如何得到一个比较 - 所以第一个元素进行0比较,第二个元素采用1,第三个采用2等 - 总结为n(n-1).
当然,只有按顺序插入(小到大或从大到小)才会出现这种情况.以恰好平衡树的顺序插入将显着更便宜.
| 归档时间： |
|
| 查看次数： |
4698 次 |
| 最近记录： |