左弦 发表于 2012-6-14 17:09:26

从二叉排序树中查找一个元素时，其时间复杂度大致为？

本帖最后由 番茄 于 2012-6-15 13:59 编辑

今天看到一个题，问从二叉排序树中查找一个元素时，其时间复杂度大致为多少？有那位数据结构高手知道，给个提示吧，谢谢了。。。

wangyexin 发表于 2012-6-14 17:09:27

log2N         

Life_On_The_Go 发表于 2012-6-14 17:28:02

RE: 从二叉排序树中查找一个元素时，其时间复杂度大致为？

O（n(n+1)/2）

Life_On_The_Go 发表于 2012-6-14 17:28:48

O（n(n+1)/2）

故乡的风 发表于 2012-6-14 23:00:49

二叉树查找元素最坏情况,遍历所有的元素，等效于顺序查找数组元素，其时间复杂度为O(n).

左弦 发表于 2012-6-15 18:34:09

故乡的风 发表于 2012-6-14 23:00 static/image/common/back.gif
二叉树查找元素最坏情况,遍历所有的元素，等效于顺序查找数组元素，其时间复杂度为O(n).

三个答案啊。。。到底那个正确啊？

左弦 发表于 2012-6-15 18:38:09

wangyexin 发表于 2012-6-14 23:01 static/image/common/back.gif
log2N

四个答案分别是，n   1    log2n   n^2?那个正确呢？

左弦 发表于 2012-6-15 18:38:58

故乡的风 发表于 2012-6-14 23:00 static/image/common/back.gif
二叉树查找元素最坏情况,遍历所有的元素，等效于顺序查找数组元素，其时间复杂度为O(n).

是log2n吧？

左弦 发表于 2012-6-15 18:45:45

Life_On_The_Go 发表于 2012-6-14 17:28 static/image/common/back.gif
O（n(n+1)/2）

应该不是把？

wangyexin 发表于 2012-6-15 20:08:47

左弦 发表于 2012-6-15 18:38 static/image/common/back.gif
四个答案分别是，n   1    log2n   n^2?那个正确呢？

log2n                     

故乡的风 发表于 2012-6-15 21:43:29

左弦 发表于 2012-6-15 18:38 static/image/common/back.gif
是log2n吧？

不好意思，看错题了。二叉排序树和折半查找类似，其时间复杂度为O(log2n)。如果是一般二叉树，就和线性表类似了，时间复杂度为O(n)。

回忆为微笑 发表于 2012-7-24 00:22:32

小甲鱼的数据结构视频是不是不更新了啊

左弦 发表于 2012-7-24 18:58:12

回忆为微笑 发表于 2012-7-24 00:22 static/image/common/back.gif
小甲鱼的数据结构视频是不是不更新了啊

不知道啊啊啊啊啊啊啊啊
页: [1]
查看完整版本: 从二叉排序树中查找一个元素时，其时间复杂度大致为？