摘要: 不等式在算法优化中的应用
【对算法,数学,计算机感兴趣的同学,欢迎关注我哈,阅读更多原创文章】
我的网站:潮汐朝夕的生活实验室
我的公众号:算法题刷刷
我的知乎:潮汐朝夕
我的github:FennelDumplings
我的leetcode:FennelDumplings
各位好,不等式经常在解决优化或最值问题时有所应用,例如均值不等式是我们高中时接触过的重要不等式,经常用于解决一些比较简单的最值问题,将函数变形去凑成均值不等式的形式,得出最值。
不等式也是算法优化时的有力手段,比如很多贪心算法的正确性都基于一些不等式。如果没有这种不等式的观察,就只能接受非贪心的算法,那时间复杂度就不优秀了。本文我们看一个例子。
题目
最初记事本上只有一个字符 ‘A’ 。你每次可以对这个记事本进行两种操作:
- Copy All(复制全部):复制这个记事本中的所有字符(不允许仅复制部分字符)。
- Paste(粘贴):粘贴 上一次 复制的字符。
给你一个数字 n ,你需要使用最少的操作次数,在记事本上输出 恰好 n 个 ‘A’ 。返回能够打印出 n 个 ‘A’ 的最少操作次数。
示例 1:
输入:3
输出:3
解释:
最初, 只有一个字符 ‘A’。
第 1 步, 使用 Copy All 操作。
第 2 步, 使用 Paste 操作来获得 ‘AA’。
第 3 步, 使用 Paste 操作来获得 ‘AAA’。示例 2:
输入:n = 1
输出:0
提示:
1 | 1 <= n <= 1000 |
题解
算法1:动态规划
定义 dp[i] 表示当前屏幕有 i 个 A,到达屏幕有 n 个 A,所需经过的最少操作次数。这里操作次数为阶段,i 是附加信息。但除了这一个附加信息还找不到最优子结构。
由于增加 A 的个数的唯一方式就是粘贴,这里面唯一变量是粘贴多少个 A。因此需要增加一个信息 j,表示当前剪切板中有 j 个 A。
刚开始时,屏幕有 1 个 A,剪切板中有 0 个 A,因此答案为 dp[1][0],第两步只能执行复制再粘贴的操作,这样剪切板中变为 1 个 A,屏幕上是 2 个 A,于是 dp[1][0]=2+dp[2][1]。
下面考虑初始化问题。当 i=n 时,已经达到了想要的 A 的个数,因此 dp[n][⋯]=0。
此外还会有无法转移到 dp[n][⋯] 的情况,也就是 i 无法整除 n,同时 j 也无法整除 n−i 的情况。这种情况记 dp[i][j]=INF。
下面考虑状态转移方程:
对于 dp[i][i],只能执行粘贴,转移到 1+dp[2i][i];
对于 dp[i][j],j<i,则可以执行粘贴,转移到 1+dp[i+j][j],也可以执行复制,转移到 1+dp[i][i],也就相当于转移到 2+dp[2i][i]。在这两种决策中选择最优的即可。
dp[i][j]=min代码 (Python)
共 O(N^{2}) 个状态,时间复杂度为 O(N^{2})。
1 | INF = int(1e9) |
算法2:数论、不等式
将 1 次复制和 x 次粘贴合到一起,记为一轮复制粘贴。
从初始的屏幕上只有 1 个 A,剪切板里没有 A 开始。经过若干轮复制粘贴,使得屏幕上有 n 个 A。
一轮复制粘贴使得原来的长度 l 变为 l(x + 1)。
假如一共进行了 k 轮,第 i 轮进行 1 次复制和 x_{i} 次粘贴。这样 k 轮复制粘贴后的总长度为:
目标是屏幕上有 n 个 A,因此就要:
记 y_{i} = 1 + x_{i},这样问题就变成了如何将 n 分解为若干个数的乘积 n = \prod\limits_{i = 1}\limits^{k}y_{i},使得总操作次数 \sum\limits_{i=1}\limits^{k}y_{i} 最小。
引理(不等式)
当 a \geq 2, b \geq 2 时,ab \geq a + b。
证明
做商:
由于 a, b \geq 2,有 \frac{1}{a} \leq \frac{1}{2},\frac{1}{b} \leq \frac{1}{2}。因此 \frac{1}{a} + \frac{1}{b} \leq 1
于是 \frac{a + b}{ab} \leq 1,即 a + b \leq ab。
\Box
假设目前将 n 分解为了 n = ab,此时的总操作次数为 a + b。b 可以进一步分解为 b = cd,若执行这步分解,则总操作次数变为 a + c + d。由上述引理,由于 c, d \geq 2,有 b = cd \geq c + d。因此 a + b \geq a + c + d,也就是总操作次数可能不变也可能变小。
这样我们就可以尽可能将 n 多分解,直至不能分解,最终会分解为若干个质数的乘积 n = p_{1}^{n_{1}}\cdots p_{k}^{n_{k}}。对应的总操作次数为 \sum\limits_{i=1}\limits^{k}n_{i}p_{i}
因此最终算法就是,对 p = 2,3,\cdots,n 的每个数进行试除,若质数 p 能整除 n,且 n 的展开式中 p 的次数为 k,则将答案 res 加 kp,将 n 更新为 \frac{n}{p^{k}},然后进行下一个质数 p,直至 n 变成 1。
时间复杂度为 O(\sqrt{N})。
代码 (C++)
1 | class Solution { |