树形常用算法

如何求 m 的 n 次幂（$m^n$）

从数学的角度来说 $m^n$ 是连续 n 个 m 相乘 $m * m * m * m...$，此算法的事件复杂度为 $O(N)$

此时，我们考虑使用快速幂算法来求解 $m^n$，快速幂算法的时间复杂度为 $O(logN)$，限制 m 为整数

快速幂算法的基本思想是：

• 求 $m^n$：如果知道了 $val_{n/2} = m^{n/2}$，则 $m^n=val_{n/2}*val_{n/2}$
• 求 $m^{n/2}$：如果知道了 $val_{n/4} = m^{n/4}$，则 $m^{n/2}=val_{n/4}*val_{n/4}$
• …
• 求 $m^1$：$val_1 = m$

以此推算，可以在 $O(logN)$ 时间复杂度内求解

function halfPowPositive(n: number, m: number): number {
  if (m === 1) {
    return n;
  }

  const half = m / 2;
  const val = halfPow(n, Math.floor(half));
  return Number.isInteger(half) ? val * val : val * val * n;
}

function halfPowNegative(n: number, m: number): number {
  if (m === -1) {
    return 1 / n;
  }

  const half = m / 2;
  const val = halfPow(n, Math.floor(half));
  return Number.isInteger(half) ? val * val : val * val * n;
}

export function halfPow(n: number, m: number): number {
  if (m === 0) {
    return 1;
  }

  return m < 0 ? halfPowNegative(n, m) : halfPowPositive(n, m);
}