免费注册 查看新帖 |

Chinaunix

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

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

论坛徽章:
0
发表于 2012-08-09 01:16 |显示全部楼层
这他喵的也能吵起来,三行代码能争出个毛,找个算导里证了两页纸以上的算法来吵,要是还吵不出个所以然,就说明这个问题O疼

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

那首先统一术语就够开几楼了。

论坛徽章:
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-08-09 01:30 |显示全部楼层
回复 80# OwnWaterloo


    如果每样都得在原地证明那算法导论估计有100米厚了,很显然就是很显然,不能因为担心某些人看不出来而不显然,要知道弱智总是有的…

论坛徽章:
0
发表于 2012-08-09 01:37 |显示全部楼层
回复 82# OwnWaterloo


    1. 那个循环不变式的正确性不显然么?1) 一定会终止 2) 如果终止,一定是答案 --> 算法正确。

    2. 周长一定为什么圆的面积最大这我还真想知道 .. 需要看什么书?

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

这楼本来就是为了将这东西说清楚,又不是算法导论。
即使是算法导论,会像66楼那样偷工减料?反正对作者来说这很明显,所以任何逻辑推理都不需要了,如果看不懂就是读者弱智了?

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-09 01:47 |显示全部楼层
hbmhalley 发表于 2012-08-09 01:37
1. 那个循环不变式的正确性不显然么?1) 一定会终止 2) 如果终止,一定是答案 --> 算法正确。

如果满足那几个条件,算法就正确。如果...那,这里的逻辑关系是显然的。
但这个前提本身呢?如何说明算法是满足那几个条件的呢?我不觉得这是显然的。


先看66楼:
starwing83 发表于 2012-08-07 20:04
忘了是在哪儿看到的了。我真正完全掌握二叉搜索就是因为理解了循环不变式的概念。其实无论upper-bound还是lower-bound或者精确查询什么的,通过循环不变式可以非常非常简单的解释。

我第一反应认为这句话是在说"解释整个算法是非常非常简单",而不是"如果...那"是非常非常简单的,不算误解吧?
然后再对比75楼,真的好意思说非常非常简单么?



hbmhalley 发表于 2012-08-09 01:37
2. 周长一定为什么圆的面积最大这我还真想知道 .. 需要看什么书?

这我也不知道,只是作为例子而已。
显而易见的结果用是可以用。但要论证的话就不能显而易见一句话带过。

论坛徽章:
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-08-09 02:26 |显示全部楼层
本帖最后由 starwing83 于 2012-08-09 02:27 编辑

回复 86# OwnWaterloo


    1. 75楼比你一楼的说明短。
2. 75楼主要解释那个如果就,说明算法符合条件的只有几个注释和一段描述,你说短不短?

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

我从一开始在意的就不是你所说的非常非常简单的解释会比我的短。
而是你所说的非常非常简单的解释,其实是包含了类似"等周长圆面积最大"这种显而易见的结论。但它们只是直觉反应,而不是解释。

再说,我在1楼可是说了很多废话的,还用ascii字符画了图的。
如果像你那样的标准,我同样可以只给出函数的含义,并且用这个含义去实现函数本身,再配几个注释 —— 其他的就是显而易见了,看不懂就是读者弱智了。
但我一开始的目的就不是为了追求短。真要追求短,撂下一句"显而易见、你懂的" —— 对我来说就是这样 —— 就完了,我何必去废功夫解释?

论坛徽章:
2
青铜圣斗士
日期:2015-11-26 06:15:59数据库技术版块每日发帖之星
日期:2016-07-24 06:20:00
发表于 2012-08-09 03:04 |显示全部楼层
本帖最后由 OwnWaterloo 于 2012-08-09 03:08 编辑

回复 87# starwing83

也就是说,和我比短?能不能短出一个数量级?
例如两人相向行走、一只苍蝇在他们之间往返飞,已知3者的速度以及两人的初始距离,求相遇时苍蝇总共走多远。
一人用较通用的微积分,而另一人注意到苍蝇不断在飞这个事实直接用时间x速度,这就是复杂程度完全不同的两种解释。(微积分更通用不是这个例子的重点)
显然 —— 我可以说显然吗? —— 没有。两者递归与循环不变式之间的对应关系我前面已经说了,一句话,就是functional与imperative的区别。


在这种数量级等同的情况下,剩下的只是叙述方式不同而已。
你说你的短,我还可以说你的不够清楚呢。
比如重要的地方我还画了图。在你看来这是不是完全疯了?这么显而易见的事?但我觉得有必要,因为我目的就不是只追求短。

类似if (p)与if (p!=0)那样,风格(style)问题而已。
在这里我选择if (p!=0)以避免不清楚if (exp)实际是if (exp!=0)的人有误会。
要平时,我也会直接写if (p)。没必要在这里刻意去追求短。

你想批评我不该选择这么verbose的方式?这也太愤青了。。。
为了向他人介绍某些事实而写的demo代码,会比平时仅为自己完成什么功能写的代码更verbose,这是很正常的事情。
为了向他人说明而写的文字,比自己在大脑里的思考更verbose,也是很正常的事。


另外,如果你想比短。可以和自己比。比如66楼与75楼。
并体会66楼到底缺了什么,以及我一开始到底是想吐槽什么。
并体会我一开始到底是在吐槽什么。

论坛徽章:
0
发表于 2012-08-09 13:03 |显示全部楼层
本帖最后由 hbmhalley 于 2012-08-09 13:12 编辑
OwnWaterloo 发表于 2012-08-09 01:47
如果满足那几个条件,那算法就正确。如果...那,这里的逻辑关系是显然的。
但这个前提本身呢?如何说明算法是满足那几个条件的呢?我不觉得这是显然的。


“如果.. 那..”的条件只有一个,就是“算法会终止”。你是指这个不够显然么?

由于始终保证 right-left>=0,且 只要right-left>0,则每次迭代会使 right-left 减小,且right-left==0时结束。

还是显然啊,就是整数长度“越来越短所以会停”而已。

“如果..那..”的推论也差不多啊,一开始答案在[left,right)里,每次排除掉的一定不是答案,因而结果一定还在[left,right)里。如果停了,那么候选集合里只剩一个元素(我不清楚你们说的是停在[i,i+1)上还是[i,i),不过没关系 差不多),显然肯定是答案。
您需要登录后才可以回帖 登录 | 注册

本版积分规则 发表回复

SACC2019中国系统架构师大会

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




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

大会官网>>
  

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

清除 Cookies - ChinaUnix - Archiver - WAP - TOP