免费注册 查看新帖 |

Chinaunix

  平台 论坛 博客 文库
最近访问板块 发新帖
楼主: OwnWaterloo

[算法][C]二叉搜索树的两路二分查找 [复制链接]

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2012-04-23 12:34 |显示全部楼层
OwnWaterloo 发表于 2012-04-22 11:13
回复 8# yulihua49

还比如基于比较的排序,比较次数下限是n*log(n),不可能会是log(n)。


我是平衡二叉树,没必要排序了吧?直接查找,应该是log(n);

论坛徽章:
4
狮子座
日期:2013-08-20 10:12:24午马
日期:2013-11-23 18:04:102015年辞旧岁徽章
日期:2015-03-03 16:54:152015亚冠之德黑兰石油
日期:2015-06-29 18:11:11
发表于 2012-04-23 12:49 来自手机 |显示全部楼层
有这么复杂么……算法导论上有详尽的说明,顺便说一下,应用循环不变式这个很好写的

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2012-04-23 13:13 |显示全部楼层
本帖最后由 yulihua49 于 2012-04-23 13:20 编辑
starwing83 发表于 2012-04-23 12:49
有这么复杂么……算法导论上有详尽的说明,顺便说一下,应用循环不变式这个很好写的

循环不变式?不懂。
哎,都说好做,都没有。

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-04-23 13:29 |显示全部楼层
很多概念对你来说根本就是一团浆糊。

1. 比如前你提到过的用二叉搜索树完成O(lgN)排序。 根本就是不可能的事情。

2.
yulihua49 发表于 2012-04-23 11:54
一个平衡的二叉树,还有必要使用二分法吗?

鉴于问题已经解决,这个问题转化成一个考题:
在一个平衡二叉树里,如何实现不等查找:
以[O(log2(N))]的代价,找到大于指定值的最小节点。


二叉搜索树的查找使用的就是二分法。 你以为只有数组那个才叫二分吗?
我只是告诉你在搜索树里,如何用两路二分法找到等价区间 —— 这个算法与二叉搜索树是否平衡根本没有关系
平衡二叉搜索树也是二叉搜索树, 它在搜索时使用与二叉搜索树相同的技巧 —— 二分。
平衡了,自然就是O(lgN);不平衡,最坏情况就是线性。

于是你说的考题,就是我这个楼的内容。 只是你自己将平衡树、 二分、O(lgN)这些概念搅和在了一起而已。

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-04-23 13:33 |显示全部楼层
yulihua49 发表于 2012-04-22 10:08
你测一下时间吧,下周我们比一比。
65535个节点的树,查找一个值需要多少时间。
使用gettimeofday就可以测到微秒级。
1微秒是允许的上限。


本来我以为你会公布源代码的。那这句话都还说得过去(我可是尽量把你往好的方向想啊)。
结果你根本就不给源代码。

yulihua49 发表于 2012-04-23 12:15
测试程序如下(不是算法):64位的。



没你这样直接用绝对时间比较性能的。 CPU都不同,绝对时间对比较有意义吗?

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-04-23 13:35 |显示全部楼层
回复 12# starwing83

本来就是很基础的东西……  难的我也不会……
你去看我在2楼提到的起因……
8页了都……
还打算申请专利呢……

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2012-04-23 14:08 |显示全部楼层
OwnWaterloo 发表于 2012-04-23 13:35
回复 12# starwing83

本来就是很基础的东西……  难的我也不会……

那是扔板砖的话,别当真。
本来就是很基础的东西,不错。
把你们的拿出来晒晒。
楼主的算一个。但我觉得不太理想,学学可以。

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2012-04-23 14:10 |显示全部楼层
本帖最后由 yulihua49 于 2012-04-23 14:15 编辑
OwnWaterloo 发表于 2012-04-23 13:33
本来我以为你会公布源代码的。那这话都还说得过去(我可是尽量把你往好的方向想啊)。
结果你根本就 ...

现在差不多都是2 .几G的X86,差不多的。-50%,+100%,都无所谓,看看数量级即可。
源代码肯定是要公布的,别着急。

论坛徽章:
0
发表于 2012-04-23 14:12 |显示全部楼层
回复 17# yulihua49


莫虚伪,伤我眼,你先自己看你自己那个帖子再来说这些屁话

论坛徽章:
15
射手座
日期:2014-11-29 19:22:4915-16赛季CBA联赛之青岛
日期:2017-11-17 13:20:09黑曼巴
日期:2017-07-13 19:13:4715-16赛季CBA联赛之四川
日期:2017-02-07 21:08:572015年亚冠纪念徽章
日期:2015-11-06 12:31:58每日论坛发贴之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-08-04 06:20:00程序设计版块每日发帖之星
日期:2015-07-12 22:20:002015亚冠之浦和红钻
日期:2015-07-08 10:10:132015亚冠之大阪钢巴
日期:2015-06-29 11:21:122015亚冠之广州恒大
日期:2015-05-22 21:55:412015年亚洲杯之伊朗
日期:2015-04-10 16:28:25
发表于 2012-04-23 14:16 |显示全部楼层
walleeee 发表于 2012-04-23 14:12
回复 17# yulihua49

把火烧到这啦?消消气。免得我又说废话。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

【数字转型 架构演进】SACC2019中国系统架构师大会
2019年10月31日~11月2日第11届中国系统架构师大会(SACC2019)将在北京隆重召开。四大主线并行的演讲模式,1个主会场、20个技术专场、超千人参与的会议规模,100+来自互联网、金融、制造业、电商等领域的嘉宾阵容,将为广大参会者提供一场最具价值的技术交流盛会。




----------------------------------------

大会官网>>
  

北京盛拓优讯信息技术有限公司. 版权所有 16024965号-6 北京市公安局海淀分局网监中心备案编号:11010802020122
中国互联网协会会员  联系我们:huangweiwei@it168.com
感谢所有关心和支持过ChinaUnix的朋友们 转载本站内容请注明原作者名及出处

清除 Cookies - ChinaUnix - Archiver - WAP - TOP