算法课程杂记 1
线性时间解决MCS问题
课堂上的分治算法解决最大子序列问题的时间复杂度为 $O(n*logn)$，然而，这种问题更加优越、更加常见的解决方式是应用动态规划的思想，即 Kadane 算法。
MCS 问题简述
即最大子序列问题：在数组的一个维度寻找连续的的子序列，使该子序列的和最大。
这种问题经常被包装成一些现实的策略问题，例如：根据股票的涨跌求算哪个时间区间入股赚得最多（当然是事后判断，要是能预测那大家都退学炒股去了hhh
算法思想
一开始接触到的是分治算法解决的思想：
- 显然，将一个数组从正中间分成两块，则所求序列有三种分布方式：在左块，在右块，横跨两块
- 在左或右的情况递归处理即可，横跨两块的情况需要从正中的坐标出发，分别向左右进行移动，找到起点在正中的左右最大子序列（复杂度：$O(n)$），再将左右找到的合并即可。
- 对这三种情况求算出的结果区最大值即可
显然，这种算法不可能是线性复杂度的
故采用动态规划的思想：
- 要利用动态规划，一般情况下需要找到比当前问题规模小 “1” 的子问题
- 故该问题转化为，求一系列以
array[i], 0 <= i < len结尾的最大子序列，其中这一系列最大子序列中最大的为所求。
算法实现
这样，核心代码就非常简单了：
int MCSofArray(int *array, int len) {
int dp[len] = {array[0]};
int maxdp = dp[0];
for(int i = 1; i < len; i++) {
dp[i] = max(dp[i-1] + array[i], array[i]);
maxdp = max(maxdp, dp[i]);
}
return maxdp;
}
该算法的时间复杂度为 $O(n)$
分治和动归的界限
或许仍有些疑问，如果我拿到一个算法问题，如何确定是用分治还是用动归思想去解决呢？
我浅薄地认为：
- 分治思想适用的问题都可以被分成两个（或者多个）子问题，这些子问题一般是该问题做除法得到的，这一点反映在时间复杂度的计算上
- 动归思想适用的问题一般可以分为多个子问题，这些子问题是该问题做减法得到的
- 显然，对于问题规模的下降速度，减法要比除法慢得多，所以“做减法”的问题如果不做转换一般不适用于分治的经典结构——递归
快速傅里叶变换
课上学习两个多项式相乘的算法时，我们很别扭地将两个多项式的乘法拆成了3个子问题，然而，最著名的解决该问题的方法则是快速傅里叶变换。
多项式的表示形式
不必多说，对于 n 次多项式，其标准型为：
$A(x) = a_0 + a_1 * x + a_2 * x^2 + \dots + a_n * x^n$
系数表示法写成：
$A = (a_0, a_1, a_2, \dots, a_n)$
点值表示法则有：
$A(x) = {(x_0, A(x_0)), (x_1, A(x_1)),\dots,(x_{n-1}, A(x_{n-1})),}$ , $x_k$ 互不相等
这个表示法是多项式乘法能被傅里叶变换优化的基础。
多项式相乘问题的 another approach
假设我们需要求的式子为：
$C(x) = A(x) * B(x)$
其中用点值表示法表示 C(x), A(x), B(x)
必然有：
$C(x) = {(x_0, A(x_0)*B(x_0)), (x_1, A(x_1)*B(x_1)),\dots,(x_{n-1}, A(x_{n-1})*B(x_{n-1})),}$ , $x_k$ 互不相等
至此，我们只需要根据 C(x) 的点表示式写出其一般多项式形式即可。
这个问题的关键有两点：
- 如何得到一个多项式的点表示式
- 如何由一个点表示式推出对应多项式
如何得到 A(x) 的点表示式
- 需要取n个不重复的点，这n个点的取法是复数域上的单位根。复数域上的单位根：将单位圆分成n份，每一份对应的复数即为选择的点：
$w_n^k = cos(2k\pi/n) + i * sin(2k\pi/n)$ - 现在知道点表示法的横坐标了，需要带入 A(x) 求出对应的纵坐标的值，直接带入计算的话，求解这n个点的时间复杂度是$O(n^2)$的，因此不可取
- 现在起要求n是2的整数次幂，如果不足的话，后面补零
- 将 A(x) 的奇数项和偶数项分开，设：
$A_1(x) = a_0 + a_2*x + … + a_{n-2}*x^{n/2-1}$
$A_2(x) = a_1 + a_3*x + … + a_{n-1}*x^{n/2-1}$
$A(x) = A_1(x^2) + x*A_2(x^2)$
- 当需要求解 $w_n^k$ 对应的纵坐标时，不妨同时关注$w_n^{k + n/2}$:
$A(w_n^k) = A_1(w_n^{2k}) + w_n^k*A_2(w_n^{2k})$
由变换可得（转化为三角形式会直观些）：
$A(w_n^k) = A_1(w_{n/2}^{k}) + w_n^k*A_2(w_{n/2}^{k})$
同样的：
$A(w_n^{k+n/2}) = A_1(w_n^{2k+n}) + w_n^{k+n/2}*A_2(w_n^{2k+n})$
变换得：
$A(w_n^{k+n/2}) = A_1(w_{n/2}^{k}) - w_n^k*A_2(w_{n/2}^{k})$
- 注意到$A(w_n^k)$ 和 $A(w_n^{k+n/2})$ 最后分解成的式子中有公共部分，则这二者可一并计算
- 故对于计算单个点对应的纵坐标，采用分治算法，时间复杂度 $T(n) = 2*T(n/2)$，为$O(logn)$
- 总时间复杂度为 $O(n*logn)$
关于如何分治：因为我们要求$A(w_n^k)$需要知道$A_1(w_{n/2}^{k})$ 和 $A_2(w_{n/2}^{k})$
可见，子问题的形式与原问题一样，但规模减半，运用分支的递归策略即可求解
如何由一个点表示式推出对应多项式
结论是：
将n个点的每个点$(w_n^k, A(w_n^k))$记作$(x_k, y_k)$，则多项式系数$a_k$为：
$a_k = 1/n * \sum(y_i * (w_n^{-k})^i), i \in [0, n-1]$
具体推导步骤见此
那对于$a_k$的计算，如何分治呢？
其实这里是一个小 trick，观察$a_k$可知，我们要计算的是一个以 $w_n^{-k}$ 为参数的多项式，这与刚刚求纵坐标的方式非常类似，做相同的处理即可，在编程上可以用同一个函数实现，总复杂度为 $O(n*logn)$
背包问题
背包问题主要有三类：
- 0-1背包问题，每个物体数量为1
- 完全背包问题，每个物体数量无限
- 多重背包问题，每个物体数量有限，为 s[i]
其中，多重背包问题可通过将同类物体视为不同转变为0-1背包问题，这里不做赘述。
状态转移方程辨析
递推式中，i 表示检索第 i 个物体，j表示当前背包重量，v 为物体价值数组，dp 存储检索完第 i 个物体时背包重量为 j 时，对应的背包价值。
0-1背包问题：
dp[i][j] = max(dp[i - 1][j], v[i]+dp[i - 1][j - w[i]])
完全背包问题：
dp[i][j] = max(dp[i - 1][j], v[i] + dp[i][j - w[i]])
可以看到，由于完全背包情况下物体数量无限，故决定是否放入标号为 i 的物体前，可能已放入标号为 i 的物体。
多项式时间复杂度中的 x 的辨析
多项式时间算法：在输入规模为x的情况下，算法能够在$O(x^k)$ 时间(k为常数)内解决该问题。
以一个最简单的问题为例，寻找 $[0, N]$ 区间内所有的素数。
大家可能会想到素数筛等算法，或者干脆的直接查表，时间复杂度为O(n)，但这个问题的输入只有一个数字 n，换算成输入规模为 $x = logn, n = 2^x$
显然，该算法的时间复杂度可以表示为 $O(2^x)$，不是多项式时间算法。
到这，你或许可以理解为什么人们对多项式时间算法如此执着追求，你可以通俗的理解，这种算法响应一个输入的相对时间代价较小；毕竟算法都是服务于人的，就像那个素数的例子，没有用户会手动把 0 到 N 全部输入进去哈哈哈~
