鱼C论坛

 找回密码
 立即注册
查看: 11346|回复: 12

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

[复制链接]
发表于 2012-6-14 17:09:26 | 显示全部楼层 |阅读模式
1鱼币
本帖最后由 番茄 于 2012-6-15 13:59 编辑

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

最佳答案

想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
发表于 2012-6-14 17:09:27 | 显示全部楼层
log2N           
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2012-6-14 17:28:02 | 显示全部楼层

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

O(n(n+1)/2)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2012-6-14 17:28:48 | 显示全部楼层
O(n(n+1)/2)
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2012-6-14 23:00:49 | 显示全部楼层
二叉树查找元素最坏情况,遍历所有的元素,等效于顺序查找数组元素,其时间复杂度为O(n).
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2012-6-15 18:34:09 | 显示全部楼层

三个答案啊。。。到底那个正确啊?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2012-6-15 18:38:09 | 显示全部楼层

四个答案分别是,n   1    log2n   n^2?那个正确呢?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2012-6-15 18:38:58 | 显示全部楼层
故乡的风 发表于 2012-6-14 23:00
二叉树查找元素最坏情况,遍历所有的元素,等效于顺序查找数组元素,其时间复杂度为O(n).

是log2n吧?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2012-6-15 18:45:45 | 显示全部楼层
Life_On_The_Go 发表于 2012-6-14 17:28
O(n(n+1)/2)

应该不是把?
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2012-6-15 20:08:47 | 显示全部楼层
左弦 发表于 2012-6-15 18:38
四个答案分别是,n   1    log2n   n^2?那个正确呢?

log2n                     
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2012-6-15 21:43:29 | 显示全部楼层

不好意思,看错题了。二叉排序树和折半查找类似,其时间复杂度为O(log2n)。如果是一般二叉树,就和线性表类似了,时间复杂度为O(n)。
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

发表于 2012-7-24 00:22:32 | 显示全部楼层
小甲鱼的数据结构视频是不是不更新了啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

 楼主| 发表于 2012-7-24 18:58:12 | 显示全部楼层
回忆为微笑 发表于 2012-7-24 00:22
小甲鱼的数据结构视频是不是不更新了啊

不知道啊啊啊啊啊啊啊啊
想知道小甲鱼最近在做啥?请访问 -> ilovefishc.com
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|鱼C工作室 ( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)

GMT+8, 2024-3-29 21:16

Powered by Discuz! X3.4

© 2001-2023 Discuz! Team.

快速回复 返回顶部 返回列表