今天的消防演习中,消防员教给我们一种在一根绳子上快速打出多个单结,从而逃出火场的方法:
第一步将绳子绕成图1的样子,即n
个绳圈。
第二步把绳头穿过所有的绳圈,然后手持绳头快速一甩,绳子经过图2的状态变成图3的结果。
这是欲紧急逃脱时使用的结,其特征是在一条绳子上连续打好几个单结。打法就如下图所示,但若不熟练的话,结与结之间很难做成等间隔。反覆练习到抓到窍门为止吧!
1
2
3
打一个单结很简单,绕一圈然后一穿就可以,绳子短或者要在绳子末端打结的话,只需 一 秒钟就搞定,不信看视频1的开头。
但是。。。如果绳子长,且要在绳子中部打结的话,就意味着要从绳圈中拉出至多一半长度的绳子,时间复杂度为O(n)
。
而要用这种“笨办法”打出n
个均匀分布的单结的话,时间复杂度也相应提升至O(n ** 2)
。
你们知道我想说什么了吧?手动滑稽
嗯,没错,O(n)
。
我在观察消防员的演示后,脑海里首先闪过的就是这个O(n)
。
第一步将绳子绕成图1的样子,即n
个绳圈,用时O(n)
。
第二步把绳头穿过所有的绳圈,然后手持绳头快速一甩,绳子经过图2的状态变成图3的结果,用时还是O(n)
。
啊哈!算法。
视频1的16:20处也是通过这个原理打结,并且:
- 结与结之间的距离基本就是左手上绳圈的周长,容易控制。
- 不需要甩绳子,不容易在这个环节上出错。
这种方法的缺(bug)点也很明显,如果真要从高楼里,用一根相当长的绳子逃生的话,左手上要拿的绳子的重量也是O(n)
。因此有必要学习将多节绳子牢固地串联起来的打结方法。
ps:
将绳子一端固定在水管等坚硬物体上的方法,消防员教我们的是视频1 9:00处的卷结。