分治策略
步骤
分解（divide）：将问题划分为一些子问题，子问题的形式与原问题一样，只是规模更小。
解决（conquer）：递归地杰出子问题。如果子问题的规模足够小，则停止递归，直接求解。
合并（Combine）：将子问题的解组合成原问题的解。
递归式
递归式（recurrence）可以帮我们刻画整个算法的运行时间。
一个常见刻画递归式的方法是画递归树。通过递归树的枝叶来试图把整个算法的步骤勾勒出来。
All articles on this blog are licensed under CC BY-NC-SA 4.0 unless otherwise stated.
Related Articles
2024-10-07
高级算法设计和分析技术
思维导图 常见算法题 常见算法题.xmind 常用数学公式 公式 名称 说明 ∑i=1ni=n(n+1)2\sum\limits_{i=1}^{n}i=\frac{n(n+1)}{2}i=1∑ni=2n(n+1) 等差数列和 1+2+3+…+n ∑i=1n(2i−1)=n2\sum\limits_{i=1}^{n}(2i-1)=n^{2}i=1∑n(2i−1)=n2 奇数和 1+3+5+…+(2n-1) ∑i=1ni2=n(n+1)(2n+1)6\sum\limits_{i=1}^{n}i^{2}=\frac{n(n+1)(2n+1)}{6}i=1∑ni2=6n(n+1)(2n+1) 平方和 12+22+32+...+n21^{2}+2^{2}+3^{2}+...+n^{2}12+22+32+...+n2 ∑i=1ni3=(n(n+1)2)2\sum\limits_{i=1}^{n}i^{3}=\left(\frac{n(n+1)}{2}\right)^{2}i=1∑ni3=(2n(n+1))2 立方和 等于平方和的平方 ∑i=0n−1...
2025-08-04
《编程之美》
序言 下水道井盖为什么是圆的 “下水道井盖是圆的，因为圆形不会掉进井口，而且圆形具有均匀分布压力的优势。” 一个屋子有一个门（门是关闭的）和3盏电灯。屋外有3个开关，分别与这3盏灯相连。你可以随意操纵这些开关，可一旦你将门打开，就不能变换开关了。确定每个开关具体管哪盏灯？ 答：将一盏灯开一段时间，再关掉，在剩余2盏灯里随机开一盏，进屋去看，发热的灯对应第一个碰的开关，亮着的灯对应开关开着的开关，灭的灯对应没碰过的开关。 游戏之乐 如何写一个程序让 cpu 占用率保持在 50%？ 不要用 if-else 来解决，要把比例转成不同的 worktime。 解法的精确与否其实取决于“多久时间内测度一次已占用的时间”和“睡眠”两类 api 的精度。 基本思路： 先计算一下某个周期内的目标时间： 假设我们使用 1s 为一个完整周期，则这个周期的 50% 为0.5s。 我们就用当前时间 + 0.5s 得到一个真正目标时间，比如当前时间在 15:06秒，目标时间就是15:06.5。如果有毫秒偏差，以此类推。 找一个无限 while 循环，内部只做两件事： 进行一个稍微复杂的数学计算，如开平...
2026-05-23
LRU 和 workingset：内核如何近似"最近使用"
上一篇把反向映射讲清楚了：内核可以从物理页找回所有映射方。一旦找到，下一个问题是：在所有缓存着的页面中，选谁回收？这就是 LRU 和 workingset 机制要回答的事。 核心问题可以压成一句话： Linux VM 无法知道未来访问序列，只能用最近访问证据、链表分层和 refault 信息近似估计 working set。 问题从哪里来 教材把 LRU 画成一个链表：每次访问把页面移到头部，回收时从尾部摘掉。理论上，这对局部性良好的负载接近最优。 实际系统无法直接实现教材 LRU。原因有三： 第一，每次内存访问都移动链表节点，开销不可承受。用户态一个循环可能每秒触发亿次内存访问，不可能每次都走内核锁链表。 第二，精确 LRU 需要全局排序。两个进程分别访问各自的页面，真正的 LRU 需要知道谁先谁后，需要一个全局时间戳或全局链表锁，NUMA 架构下这是严重瓶颈。 第三，内核的信息来源有限。硬件只提供 PTE 的 Accessed 位：访问过就置 1，内核定期清除再观察是否重新置 1。这是一个"采样"而不是"时间戳"。 因此 Linu...
2018-11-14
散列算法
散列算法概述 散列函数（Hash Function）是一种将任意长度的输入数据映射为固定长度输出的函数，该输出称为散列值或哈希值。散列算法在计算机科学中具有广泛应用，尤其在密码学和数据完整性校验领域。 核心性质 一个优秀的散列函数应具备以下核心性质： 确定性：相同的输入始终产生相同的输出。这是散列函数的基本要求，确保了散列值的一致性和可验证性。 单向性：从散列值无法反向推导出原始输入。这一性质使散列函数适用于密码存储等场景，即使数据库泄露，攻击者也无法直接获取明文密码。 雪崩效应：输入数据的微小变化会导致输出散列值的剧烈变化。修改输入的任意一位，输出的散列值应有约50%的位发生变化。这一特性保证了散列值对输入的高度敏感性。 抗碰撞性：难以找到两个不同的输入产生相同的散列值。抗碰撞性分为弱抗碰撞性（给定输入，难以找到另一个输入产生相同散列值）和强抗碰撞性（难以找到任意两个不同输入产生相同散列值）。 常见散列算法家族 MD5 MD5（Message Digest Algorithm 5）输出128位散列值，曾广泛应用于文件校验和密码存储。然而，MD5已被证明存在严...