如何计算2022ⁿ？算法正确性证明与时间复杂度上界求解

1. 暴力迭代乘法（你提到的n-1次乘法实现） #

思路 #

初始化结果为2022，对n≥1的情况执行n-1次乘法操作：result = result * 2022；若n=0，直接返回1（符合2022⁰=1的定义）。

正确性证明（数学归纳法） #

• 基例：
  • n=0时，返回1，符合幂的定义，成立；
  • n=1时，无需执行乘法，返回2022，符合2022¹=2022，成立。
• 归纳假设：假设对于任意正整数k，执行k-1次乘法后能正确得到2022ᵏ。
• 归纳步骤：计算2022ᵏ⁺¹时，在2022ᵏ的基础上再执行一次乘法，得到2022ᵏ * 2022 = 2022ᵏ⁺¹，根据归纳假设，2022ᵏ结果正确，因此最终结果成立。

时间复杂度 #

最多执行n次乘法操作（n=0时为0次），每次乘法视为常数时间操作（不考虑大数乘法的位数影响时），因此时间复杂度上界为O(n)。

2. 快速幂算法（二进制幂，更高效的方案） #

思路 #

利用指数n的二进制分解特性，将幂运算转化为更少的乘法操作。例如n的二进制表示为b₀ + b₁*2 + b₂*2² + ... + bₘ*2ᵐ（bᵢ∈{0,1}），则：
2022ⁿ = 2022^b₀ * (2022²)^b₁ * (2022⁴)^b₂ * ... * (2022^2ᵐ)^bₘ
通过迭代平方底数，并根据当前二进制位是否为1，决定是否将当前底数乘入结果。

伪代码实现：

def fast_pow(base, exponent):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result *= base
        base *= base
        exponent = exponent // 2
    return result

正确性证明（数学归纳法） #

• 基例：
  • exponent=0时，返回1，符合base⁰=1，成立；
  • exponent=1时，返回base，符合base¹=base，成立。
• 归纳假设：假设对于任意非负整数k，算法能正确返回baseᵏ。
• 归纳步骤：分两种情况讨论：
  1. 若k为偶数（k=2m）：算法中底数变为base²，指数变为m，根据归纳假设，返回(base²)^m = base^(2m) = baseᵏ，正确；
  2. 若k为奇数（k=2m+1）：算法先将结果乘以base（此时result=base），再将底数变为base²，指数变为m，最终返回base * (base²)^m = base^(2m+1) = baseᵏ，正确。

时间复杂度 #

每次循环将指数减半，循环次数为O(log₂n)，每次循环仅包含常数次乘法操作，因此时间复杂度上界为O(log n)，远优于暴力乘法的O(n)。

3. 基于2022分解形式的乘法优化 #

你给出的2022分解形式可用于优化单次乘法的运算量（不改变整体算法的时间复杂度阶数，但能减少单步计算的操作数）：

• 分解2022 = 2000 + 20 + 2：计算2022 * x时，拆分为2000*x + 20*x + 2*x，其中2000*x可通过位运算（x << 11 + x << 9，因为2000=2^11 + 2^9）替代乘法，减少计算步骤；
• 分解2022 = 20*101 + 2：计算2022*x时，转化为20*101*x + 2*x = (x*101)<<4 + (x*101)<<2 + 2*x，同样利用位运算简化乘法。

这类优化适合底层实现或大数运算场景，但不会改变算法的时间复杂度上界（比如结合快速幂仍为O(log n)）。

内容的提问来源于stack exchange，提问作者Anonymous_00011