迭代幂运算/重幂的介绍与其Python代码实现

数学中的迭代幂运算/重幂是什么？

迭代幂运算（重幂）是数学中的一种运算，涉及到反复进行幂次运算。它是超运算序列的一部分，该序列延伸了加法、乘法和幂运算。在迭代幂运算中，一个数自乘多次，直到达到指定的次数。

一个数a迭代幂的高度n通常表示为：，也就是把n写在a的左上角，（也可以记作：a↑↑n）这表示a被迭代n次。

例如：

• （简单恒等式）
• （a自乘一次）
• （a的幂次为a自乘）
• ，依此类推。

在迭代幂运算的上下文中， 通常未定义或没有普遍共识。然而，一些数学惯例建议对于任何 ，，类似于在幂运算中对任何非零的 有 的情况。

迭代幂运算示例

让我们评估 （读作“2迭代到高度3”）：

因此

迭代幂/重幂运算的通用性质

• 非交换性：迭代幂运算不是交换的，这意味着
• 增长速度非常快：迭代幂运算增长非常快。即使是小数也会因为幂运算的快速增长而导致非常大的结果。

迭代幂运算/重幂在基础数学中较少见，但在某些高级数学领域中发挥作用，特别是在涉及极大数的领域，如大数理论和计算机科学中。

用 Python 计算迭代幂运算

以下是两个计算迭代幂运算的Python函数。第一个使用递归，第二个使用迭代。

在两个函数中，我们在开始时添加了对 n = 0 的检查。如果 n 为 0，则函数返回 1，否则继续处理。这种方式使函数能够按照任意数的迭代幂高为0时为1的惯例处理 n=0 的情况。

递归函数计算迭代幂

递归函数：此函数将自己调用，n 的高度递减1，直到达到1，此时返回基数a。这就实现了从上到下构建指数链的效果。

1
2
3
4
5
6
7

@lru.cache(None)  ## 缓存函数
def tetration_recursive(a, n):
    if n == 0:
        return 1
    if n == 1:
        return a
    return a ** tetration_recursive(a, n - 1)

@lru.cache(None)  ## 缓存函数
def tetration_recursive(a, n):
    if n == 0:
        return 1
    if n == 1:
        return a
    return a ** tetration_recursive(a, n - 1)

递归计算迭代幂的函数理论上可以进行尾优化。在尾递归中，递归调用是函数中的最后一个操作，这样某些编译器或解释器可以通过重用相同的堆栈帧来优化调用堆栈的使用。这可以通过消除每个递归调用的额外堆栈帧需求来将空间复杂度降到 O(1)。

然而，当前的递归实现并不是尾递归的，因为递归调用嵌套在一个幂运算中：

1

return a ** tetration_recursive(a, n - 1)

return a ** tetration_recursive(a, n - 1)

这里，幂运算依赖于递归调用的结果，所以在完成当前调用之前必须计算出结果，从而阻止了尾递归优化。

迭代函数计算迭代幂

迭代函数：此函数使用 for 循环遍历高度 n，通过在每次迭代中更新幂运算的结果，来从下至上计算结果。

1
2
3
4
5
6
7

def tetration_iterative(a, n):
    if n == 0:
        return 1
    result = a
    for _ in range(1, n):
        result = a ** result
    return result

def tetration_iterative(a, n):
    if n == 0:
        return 1
    result = a
    for _ in range(1, n):
        result = a ** result
    return result

迭代幂算法的时间/空间复杂度

Python函数计算迭代幂的时间和空间复杂度取决于其递归或迭代实现。让我们分析两种实现。

递归函数的复杂度

时间复杂度：

• 每次递归调用都会与之前的调用结果进行一次幂运算。
• 总共有n-1次递归调用，所以该函数被调用了O(n)次。
• 然而，像 的幂运算需要 的时间。
• 因此，对于较大的 n 值，由于幂次的增长，其时间复杂度会呈指数增长。
• 这导致总的时间复杂度大约为 ，有n层，这意味着增长速度非常快

空间复杂度：

• 由于这是一个递归函数，每次调用都需要堆栈空间。
• 递归的最大深度为 n，所以空间复杂度为 O(n)。

迭代函数的复杂度

时间复杂度：

• 与递归版本一样，该函数迭代 n – 1 次
• 每次迭代涉及计算 的幂次，这个结果会呈指数增长。
• 因此，时间复杂度也成为 ，有n层，因为每一步都是指数级增长。

空间复杂度：

• 此迭代版本仅需要少量额外空间用于 result 变量等，因此它的额外空间复杂度为 O(1)。
• 然而，结果本身可能会变得非常大，如果 a 和 n 很大，可能需要大量内存来存储。

由于反复幂次的快速增长，这两种实现的时间复杂度都非常高，对于较大的值变得不可行。递归版本由于调用堆栈的使用空间复杂度为 O(n)，而迭代版本的辅助空间复杂度为 O(1)，但仍然需要处理极大数，这可能会间接影响内存使用。

英文：Tetration Operator in Math Simply Explained with Python Algorithms