购买
下载掌阅APP,畅读海量书库
立即打开
畅读海量书库
扫码下载掌阅APP

2.2.6 创造历史

米尔嘉一边转着我的自动铅笔一边说:

“顺序查找算法的运行步数是 4M-3S+5 ,带有哨兵的顺序查找算法的运行步数是 3M-3S+7 。也就是说,加上哨兵后,运行步数变为原来的 \frac{3}{4} 左右。”

\frac{3}{4} 是怎么得出的呢?”

M 的系数的比值。”米尔嘉说,“当 M 变得很大时,可以将 4M-3S+5 看作 4M ,将 3M-3S+7 看作 3M 。”

“快了大约25%。”理纱补充道。

米尔嘉接着说:

“先明确 前提条件 ,再求算法的运行步数,这样我们就能够 定量评估 算法的速度。如果能定量评估,便能得出像‘快了 大约25% ’这样的具体数值,而不是仅仅停留在‘很快’的层面上。通过定量评估,我们就能够有理有据地区分算法的优劣。”

“原来如此。”我说。

“明确了前提条件的定量评估,不仅能被某 一个人 利用,还能被 其他 人利用、验证、改良,甚至可以用于其他算法的分析。”米尔嘉说。

“‘明确了前提条件的定量评估’……这、这就像创造历史一样啊。”泰朵拉想入非非,“即便评估的人不在了,其他人……未来的人也可以使用。自己的思想,超越自己留存下去——这是对人类的贡献啊!”

“泰朵拉,真了不起啊。”我不由得感叹泰朵拉思想的广度。

“只是,有一点需要注意。”米尔嘉竖起食指说,“要是像用显微镜那样将注意力全部放在算法的细微差异上,就会忽视大的共同点。要妥善处理这个问题,可以使用 渐近分析 的方法。分析复杂问题的时候,我们要——”

“顺序查找算法是 O(n) [1] 的。”理纱打断了米尔嘉。

“你是理解了 O(n) 的意思才这么说的吗?”米尔嘉紧接着问道。

理纱沉默了一会儿,小声回答:

“……不是。”

米尔嘉面前的理纱像小狗一样。

“不过是说出了一知半解的单词啊。”

噢哟,这挑衅的话语。

理纱紧紧地瞪着米尔嘉。

米尔嘉用冰冷的眼神回应。

“那、那个……”泰朵拉不知所措。

无声地对视了好一会儿,理纱咂了咂舌,错开了视线。

几乎没人能瞪得过米尔嘉。

“放学时间到了。”

噢,拳击场的铃声响了……啊不,是图书管理员瑞谷老师的提醒。瑞谷女史 总是在放学时间准时通知学生回家。通知完后,女史朝我们这边瞄了一眼,回到了管理员办公室。

[1] O(n) 的读法有:欧·恩、大欧·恩、big o en、order en,等等。 lTkG7uxsK+oHeEByxC7FyURkm+bxB5awjjb5HpiphGoa66DY37lVXepu4/sBuBkF

点击中间区域
呼出菜单
上一章
目录
下一章
×