seegongsik
我的单词本
算法

劈成两半去攻克

一个人去叠一大堆衣服,叫人发怵。可要是劈成两半,一半交给弟弟呢?两个人各叠一小堆,最后合到一起就完了。大问题也一样。劈成两半,各自解开,再合回来就行。

01

劈成两半

前面说过,大活
拆成小步骤。
这里再进一步。
把一个问题的大块
劈成两半。
那一半又劈成两半,
再劈成两半。
慢慢变成一小块一小块。

8
一整块。点一下,劈成两半。

点一块,劈成两半。每点一下就一半一半地分开,慢慢成了小块。

每劈一次,
要应付的量就少一半。
大堆叫人发怵,
可一小块
好对付多了。
正是在字典里
一半一半地切着找词
那个感觉。

02

两块互不重叠

这里有一件很要紧的事。
劈成两半的两块,
彼此互不重叠。
左边那堆和右边那堆,
不会共用同一件衣服。
所以一边干过的活,
另一边不必再干一遍。
两边完全分开。

重叠部分
0
把两块一个个点亮看看。

点两块照一照。没有一处重叠。彼此分开(独立),各自解也不会撞上。

互不重叠这个性质,
别小看它。
块互不重叠,
一边的答案
就不会毁了另一边的。
往后碰上会重叠的问题,
那就是另一回事了。
那是另一条路。

03

解开那一小块

一直劈成两半,
就到了再也劈不动的
极小一块。
像一件衣服、
一个数字那样。
它太小了,
用不着费神,
立刻就解开。

最小的几块。一个个点,立刻解开。

点最小的一块(到底了)立刻解。小到再也劈不动,省心就解开(绿色)。

我们不去
硬着头皮一口气解大问题。
一直劈到底,
只把好解的小块
一个一个解掉。
把一件难事,
换成了
好几件易事。

04

合着往上叠

有了小答案,
这就反过来往上走。
把两个小答案合成
稍大一点的,
再把那两个合成
更大的。
劈了多少就合多少,
最顶上立起整个答案。

1
1
1
1
1
1
1
1
解好的小块 8 个。点一下,两两往上合。

点解好的块往上合。两块合成一块,再合成一块。顶上凑齐整个答案。

劈的时候往下,
合的时候往上。
块没重叠,
合起来也干净。
把左边的答案和右边的答案
挨着接上就行。
这,正是
劈成两半去攻克。

05

劈、解、合

汇成一句话,是这样。
劈成两半,
各自解开不重叠的块,
再合着往上叠。
在字典里一半一半地找,
把牌一半一半地分着排,
都是这一个框架。
大东西,一劈就小了。

从第一步起依次点,跟着走一圈。

依次点三个步子走一圈。劈成两半 → 解开小块 → 合着往上。块不重叠,正是关键。

这里的块,
彼此干干净净地分着。
所以解过一回的块,
用不着再解一遍。
可要是块
彼此重叠,同一个东西
得反复重解呢?
下一讲,我们就到那个岔路口。

一句话总结大问题,靠劈成两半、各自解开、再合回来去攻克。关键在于:劈出来的两块互不重叠。一边干过的活,另一边不必再干一遍。小到再也劈不动了,就立刻解,把解好的块往上合,整个答案就出来了。二分查找也好、归并排序也好,都是这个框架。块互不重叠,正是这法子的力量所在。
算法
如果有帮助,请支持我们