分而治之：编程算法背后的哲学智慧

分而治之好！

♥ 1775 ↩ 65

这阵子给孩子讲故事 发现人类大部分智慧，都在儿童时期讲过 尤其是曹冲称象 1把一个困难问题转换为一个等价的相对容易解决的问题 2把一个大问题转化为一群容易解决的小问题的和

♥ 316 ↩ 14

捞一捞自己的视频，并多说两句 0. 快速排序的图确实做错了，33和27颠倒了[笑哭]视频仓促，还请多多见谅 1. 结尾砖块的例子，很多人在意最一开始抠掉的缺口是任意的，但分治递归后每次都在角落，这是不是不一样？其实这不打紧，只要问题本身符合“边长为2的幂次的正方形抠掉一格用L形拼”这种结构，而我们的解决方法也只依赖于这个形式，到2x2的最后局部这个问题变成平凡的空缺就是L形，那么整个问题就一定能解决 2. 快排的标准怎么选？有取中间下标和随机两种，前者最坏情况下退化到平方级别，所以一般加随机化

♥ 241 ↩ 6

现实中可以考虑插排，因为现实中可以在查找位置优化成O(log n)的同时把插入优化为O(1)，并且对同一个数与多个数比较的时间消耗更少

♥ 227 ↩ 22

分享一个基于分治思想构建的二分高速加法器[脱单doge]

♥ 117 ↩ 20

唉，你说你这个 Bilibili 啊，反复推这个视频干嘛呢？ 算了算了，我这个 OIer 再给大家补充点知识吧： 其实视频末尾的分治题有一道非常类似的题目： P10085 【GDKOI2024 提高组】 染色 我在这里简单描述一下题意： 给定一个2^n×2^n的01矩阵， 每次可以将一个十字形的5个数字反转， 请构造出一种翻转方式使得所有数字都为0。 （对于 100% 的数据 n≤11）

♥ 103 ↩ 13

怎么找到用来分A堆和B堆的那个最好的标准。比如有10个数分成A5个，B5个这样寻找的次数应该比A6个和B4个好一些。

♥ 56 ↩ 10

@漫士沉思录 04:08第5行33和27排反了[吃瓜]

♥ 55 ↩ 2

漫士老师也开始做计算机学的内容啦~~好激动！！ （早就知道漫士会写程序了……manim引擎是Python的一个库，需要Python代码驱动） 知识点总结： 分治，即分而治之，计算机算法思维的一个重要部分，通过将一个问题划分为同样类型的子问题，从而用局部解求出最终解的思维。这不仅可以用在编程与计算机学，更可以用在实际生活当中，为我们的工作提高效率。 （其实漫士上次的杨辉三角也有分治的影子，如果在计算机上需要显示或生成谢尔宾斯基三角形，可以用到分治的方式，各位可以自行思考哦） 知识点拓展： 要使用分治必须满足问题具备以下性质：能够分割、子问题与整体一致、子问题互不影响（子问题独立）、拥有基础情况（base case，即不可分割的子问题）。 漫士提到的快速排序以及拼图问题，都具备以上性质。这里提一下，有人可能不理解基础情况。在快速排序中，基础情况就是序列中只剩下单个数字的时候，因为这是子问题不可分割且可以直接得到答案；在拼图问题中，基础情况就是2*2的方格，此时放置拼图只有一种方案，且不能继续分割（单个格子你怎么放？） 而子问题互不影响的意思就是，子问题A的解法不会影响子问题B的结果，即子问题A和B可以单独求解而不用考虑是否会对彼此造成影响。 分治的应用： 在编程中，分治问题通常使用递归解决，因为递归函数就是一个函数调用其本身（想想斐波那契数列的递归表示，数学中也有分治！） 分治算法的例子：快速排序、归并排序、深度优先搜索（DFS）、堆排序、矩乘（矩阵乘法）、二分搜索、分治傅里叶变换等。 分治数据结构的例子：二叉搜索树、AVL平衡树、Treap平衡树、线段树、树状数组等。 分而治之，人类思维最伟大的产物。

♥ 50 ↩ 4

漫士老师突然高产[脱单doge]

♥ 46 ↩ 3

平方根倒数算法[doge] 这个好玩

♥ 33 ↩ 2

[星星眼]

♥ 35 ↩ 13

最后的铺地砖问题可以最终转化为“在2x2的格子里抠掉一个格子，用L形地砖铺满”的方法。而这个问题一眼就能看出来，即把L形地砖塞进剩余的三个格子里

♥ 28

如果是现实中分卷子，我想大多数人应该是先拿一张，再将下一张拿出来做分数对比，以此类推，将分数放至合适位置。 如果想从电脑上表达出来，就是将a1提取，然后再将取出a2对比，大排后小排前，往后的则在中间数进行对比，同理，同时，如果对于排序中的插叙很难，那将所有的子集全部单个排列，从数据上标记他们的位置，位置改变，数字也改变，最终在由他们数字排列，这个方法同样可以运用在博主讲的化整为零的方法，应该可以提升效率。

♥ 32 ↩ 4

看到标题就冲进来：宇宙的终极问题是排队问题，宇宙的本源是增删改查

♥ 21

为什么可以分成4个而仍然有解，为什么是从中间分，这难道不是得先证明可行性吗？ 而且紧接着后面还说了可以用这个思想递归，但是从这个例子来看，再往下一层嵌套一层，也就是把4*4分成4个2*2的时候，就无解了

♥ 20 ↩ 18

下次能安排动态规划吗[脱单doge]

♥ 13

关于快排有个问题 首先，快排期望时间复杂度为 O(nlogn) ，但是是可以卡成 O(n^2) 的，比如说让整个序列中的元素全部相等，每次选的分界值是一样的，复杂度的递推式为：T(n)=T(n-1)+O(n)，通过主定理分析可知总复杂度为 O(n^2) 。如果是讲分治的话其实归并排序更适合，更能体现出分治的高效，而且还能处理逆序对问题。 C++中的sort函数据说是插入排序+快速排序+堆排序。Python和Java据说是用Tim排序实现的。 然后就可以拓展，比如说 cdq分治，线段树分治，根号分治(bushi)[doge]

♥ 12 ↩ 4

但是，这一类的算法能否实际用在实体文件排序呢？ 公司成立以来，每个月会向一批乙方收租，到现在计18个月。这些乙方分布在公司的4层楼中，平均每层楼有30个不同的乙方（带层内编号）。现在，领导要我把这18个月的所有纸质收租文件按月份/楼层/乙方层内编号三级顺序进行排序。快排或者其他分治算法是否适合这个场景呢？

♥ 11 ↩ 11