为什么数组下标是从 0 开始,而不从 1 开始?
这个问题 Dijkstra 已经解答过了,没错,就是你知道的 Dijkstra,Dijkstra 最短路径算法,荷兰语全名是 Edsger Wybe Dijkstra,于 1972 年获得了图灵奖,除了上面说的最短路径算法,还有众所周知的信号量和 PV 原语、银行家算法等也是这位巨佬提出的。
原文在这里:https://www.cs.utexas.edu/users/EWD/transcriptions/EWD08xx/EWD831.html,感兴趣的小伙伴可以去看下全文,下面我总结几段核心的观点。
首先来看个案例,如何用一个不等式(或者说表达式)来表示 [2,3,4,5,6,7,8,9,10,11,12]
这个连续的整数序列(一共 11 个数)?
假设 i
是一个整数,那么我们能够迅速地写出如下四个符合上述连续序列的不等式:
1)2 <= i < 13
2)1 < i <= 12
3)2 <= i <= 12
4)1 < i < 13
以上四个不等式均满足要求,那是否有理由选择其中的一种而不是另一种?
Dijkstra 说有的,选 1 和 2,因为这俩不等式有个很突出的点,就是不等式边界的差(不等式右边 - 不等式左边)正好等于连续序列的长度。
这里可以排除掉 3 和 4,那么 1 和 2 该如何选出最优的表示?
1 和 2 不等式的区别就在于:
1 不等式左边(下界)等于序列中的最小值,不等式右边(上界)大于序列中的最大值。 2 不等式左边(下界)小于序列中的最小值,不等式右边(上界)等于序列中的最大值。
对于第 2 个不等式来说,下界小于序列中的最小值,这会出现一个问题,比如我们的连续序列是 [0,1,2,3,4]
。
那么按照第 2 个不等式的写法,不等式的左边就是 -1,-1 是非自然数,而我们需要表示的连续序列是自然数序列,所以第 2 个不等式很不优雅:我们需要用一个非自然数来作为全是自然数的序列的下界。
因此,综上所述,不等式 1 是最优雅的选择。
那么,选出一个看着非常顺眼的不等式来表达长度为 N 的连续序列之后,下一个令人烦恼的问题是该为起始元素分配什么下标值?
遵循不等式 1 的规则:
当从下标 1 开始时,下标范围 1 ≤ i < N+1
。当从下标 0 开始时,下标范围 0 ≤ i < N
。
哪个更优雅?
Dijkstra 是这样解释的:从下标 0 开始能够给出更好的不等式,因为元素的下标就等于序列中它前面的元素数(或者说 “偏移量”)。
问题解决!
- EOF -
关注「程序员的那些事」加星标,不错过圈内事
点赞和在看就是最大的支持❤️
关注公众号:拾黑(shiheibook)了解更多
[广告]赞助链接:
四季很好,只要有你,文娱排行榜:https://www.yaopaiming.com/
让资讯触达的更精准有趣:https://www.0xu.cn/
随时掌握互联网精彩
- 1 澳门是伟大祖国的一方宝地 7932869
- 2 女子穿板鞋爬山回家脱鞋时被吓一跳 7914675
- 3 张雨绮 为了讨大家喜欢才穿成这样 7879295
- 4 2024 向上的中国 7798688
- 5 72岁老人3年拍100部短剧 7637638
- 6 免费升级宽带后家里成“电诈中心” 7534862
- 7 90%烧伤男生父亲:对方让我高抬贵手 7410566
- 8 9岁女孩胃里取出直径4厘米头发团 7343268
- 9 春熙路不能随便开直播了 7273128
- 10 男子网贷1000元3天内需还2000元 7126535