算法模式：减治法

D瓜哥
算法
算法模式：减治法

在上一篇文章 算法模式：拓扑排序 介绍一种可用于处理节点前后顺序的算法模式：拓扑排序。本篇文章，介绍一种有魔力的，可以将复杂问题化繁为简，化腐朽为神奇的算法模式：减治法。

减治法

D瓜哥最早知道减治法是在 《算法设计与分析基础》 中。这里也直接引用该书的介绍。

减治(decrease-and-conquer)技术利用了一个问题给定实例的解和同样问题较小实例的解之间的某种关系。自底向上版本往往是迭代实现的，从求解问题的一个较小实例开始，该方法有时也称为增量法(Incremental Approach)。

减治法有3种主要的变化形式：

  • 减去一个常量。在减常量(decrease-by-a-constant)变化形式中，每次算法迭代总是从实例中减去一个相同的常量。

    • 插入排序

  • 减去一个常量因子。减常因子(decrease-by-a-constant-factor)技术意味着在算法的每次迭代中，总是从实例的规模中减去一个相同的常数因子。在大多数应用中，这样的常数因子等于2，其实就是减半。

    • 二分查找

  • 减去的规模是可变的。在减治法的减可变规模(variable-size-decrease)变化形式中，算法在每次迭代时，规模减小的模式都是不同的。

    • 计算最大公约数的欧几里得算法是这种情况的一个很好的例子。 \$gcd(m, n)=gcd(n,m mod n)\$

LeetCode 50. Pow(x, n)

LeetCode - 50. Pow(x, n)

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

  • -100.0 < x < 100.0

  • -231 <= n <= 231-1

  • n 是一个整数

  • 要么 x 不为零，要么 n > 0 。

  • -104 <= xn <= 104

思路分析

对于 \$f(x,n)=x^n\$，有两种情况：

  • 如 n 为奇数，则 \$f(x,n)=x^n = x*(x^((n-1)/2))^2\$

  • 如 n 为偶数，则 \$f(x,n)=x^n = (x^(n/2))^2\$

这样 \$x^((n-1)/2)\$ 或 \$x^(n/2)\$ 只需要计算一次，重复利用，每次就可以减少一半的计算量。代码如下：

/**
 * @author D瓜哥 · https://www.diguage.com
 * @since 2025-04-07 14:26:30
 */
public double myPow(double x, long n) {
  if (x == 0) {
    return 0;
  }
  if (n == 0) {
    return 1;
  }
  boolean negative = n < 0;
  n = Math.abs(n);
  double result = 1;
  double bin = myPow(x, n / 2);
  if (n % 2 == 1) {
    result = x * bin * bin;
  } else {
    result = bin * bin;
  }
  return negative ? 1 / result : result;
}

小结

除此之外，前面介绍的 算法模式：拓扑排序、欧几里得辗转求余法、二分查以及插入排序等，也都是减治法的典型案例。