快速幂算法
这是一种简单计算乘方运算的算法，其时间复杂度为$O(logn)$。
例如：我们想计算$5^12$?那我们该怎么尽量快的去计算？
最简单粗暴的方法就是直接将5自乘11次，使用计算机的话很快就能计算出，就算是人工计算也花不了多久。
但如果这个指数很大呢？
有一个简单方法可以减少计算量，就以上面的例子来说，在首次计算$5^2=5*5=25$，第二次计算$5^4=25*25=625$，第三次计算$5^8=625*625=390625$，最后一次计算就可以直接$5^12=5^8*5^4=244140625$。
这个方法直接就让原本需要11次的计算减少到4次，而快速幂算法也与此类似，都是一种二分思路，以下将介绍两种快速幂算法：递归快速幂与非递归快速幂。
递归快速幂
递归方程如下：
$$ a^n=\left\{ \begin{array}{rcl} a^{n-1} & & if \ n \ is \ odd\\ a^{\frac{n}{2}}*a^{\frac{n}{2}} & & if \ n \ is \ even \ but \ not \ 0\\ 1 & & if \ n=0 \end{array} \right. $$
根据上面的递归方法，可以得出最优的计算步骤。
非递归快速幂
根据上面所讲的知识，我们不妨将指数转化为2进制，也就是说$5^{(12)_{10}}=5^{(1100)_2}$。
仔细看等式右边的一项，可以将其化为$5^{1000}*5^{100}*5^{00}*5^{0}$，当然，后面两项均为1，但这样分析下来，可以发现整个运算实际上仅需要$5^{1000}，5^{100}$两项，总共进行3次乘方运算、1次乘法运算就可以算出结果。
同理，此方法推广到任意的乘方运算$x^n$中均可将$n$转化为2进制，然后构造出最优运算过程。
近似松弛与最大割
近似松弛
近似松弛（approximate relaxation）是一种在优化问题中用于近似处理约束条件的技术。
在许多优化问题中，通常需要满足一些约束条件。然而，有时这些约束条件很难或无法精确地满足，这时可以使用近似松弛来处理这些约束。
近似松弛的基本思想是在优化过程中放松对某些约束条件的严格满足，以获得一个更容易求解的优化问题。这种方法可能会导致得到的解不是最优解，但可以在较短的时间内获得一个可接受的近似解。
例如，可以使用线性近似模型来近似描述一个非线性约束条件，或者使用离散模型来近似描述一个连续的约束条件。
假设有一个优化问题，目标是最小化一个函数$f(x) = x^2$，约束条件是$x$必须在$[0, 1]$的范围内。
一种简单的近似松弛方法是使用线性模型来近似$f(x) = x^2$，即假设$f(x) \approx mx + b$。我们可以通过在$[0, 1]$范围内选择一些点计算它们的函数值，然后使用最小二乘法来计算$m$和$b$的值。假设选择了x = 0, 0.5, 1这三个点，并计算了对应的函数值，得到以下数据：
$$ \begin{array}{c|l}
x & f(x) \
0 & 0 \
0.5 & 0.25 \
1 & 1 \
\end{array} $$
可以用最小二乘法来计算$m$和$b$的值，得到$m = 1，b = 0$。因此，可以近似的认为$f(x) = x$。
现在可以将原来的约束条件放宽为$x$必须在$[0, 1]$的范围内，同时最小化函数$f(x) = x$。这个问题的最优解是$x = 0$，因为0是最小值点。虽然这个解不是原来问题的最优解，但它是在较短的时间内获得的近似解。
最大割
首先，最大割问题是一个经典的图论问题，它的目标是将图中的顶点划分为两个或多个不相交的子集，使得划分后的割边数最多。在一个简单的图中，割边是指连接两个子集的边。
然而，对于大型复杂的图，最大割问题是一个$NP-hard$问题，它没有有效的求解方法。因此，通常使用近似算法来获得一个近似解。
近似松弛是一种常用的近似算法，它通过放松对某些约束条件的严格满足来简化问题。在最大割问题中，一种常见的近似松弛方法是通过限制每个顶点的度数（即与该顶点相连的边数）来简化问题。
例如，考虑一个包含$n$个顶点和$m$条边的图$G$。我们可以通过限制每个顶点的度数来得到一个简化的图$G'$，其中每个顶点的度数不超过一个给定值$k$。这个简化的图G'是一个$k$度图。
在$k$度图中，我们可以使用贪心算法来求解最大割问题。具体来说，我们可以按照顶点的度数从大到小排序，并将度数最高的顶点分配给一个子集，然后将其与另一个子集相连的边删除。然后，我们继续对剩余的顶点重复这个过程，直到所有的顶点都被分配到一个子集为止。
这种贪心算法可以在多项式时间内求解k-度图的最大割问题。然而，由于我们通过限制每个顶点的度数来简化了问题，因此这种方法获得的解可能不是原始图G的最大割问题的最优解。
总结来说，通过限制每个顶点的度数来简化图并使用贪心算法求解最大割问题是一种常见的近似松弛方法。虽然这种方法不能保证获得最优解，但它可以在较短的时间内获得一个可接受的近似解。