登录
迭代幂运算/重幂的介绍与其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。这就实现了从上到下构建指数链的效果。
@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)。
然而，当前的递归实现并不是尾递归的，因为递归调用嵌套在一个幂运算中：
return a ** tetration_recursive(a, n - 1)
这里，幂运算依赖于递归调用的结果，所以在完成当前调用之前必须计算出结果，从而阻止了尾递归优化。
迭代函数计算迭代幂
迭代函数：此函数使用 for 循环遍历高度 n，通过在每次迭代中更新幂运算的结果，来从下至上计算结果。
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
本文一共 1253 个汉字, 你数一下对不对.
相关文章：
- 按揭贷款(房贷,车贷) 每月还贷计算器 去年给银行借了17万英镑 买了20万7500英镑的房子, 25年还清. 前2年是定率 Fix Rate 的合同 (年利率2.49%). 每个月大概是还 700多英镑. 有很多种还贷的计算方式, 定率/每月固定 是比较常用的. 简单来说就是 每个月交的钱是...
- 智能手机 HTC One M9 使用测评 虽然我对手机要求不高, 远远没有像追求VPS服务器一样, 但是怎么算来两年内换了四个手机, 先是三星 S4 用了一年多, 然后 Nokia Lumia 635 Windows Phone, 后来又是 BLU, 半年多前换了...
- 英国房子的EPC节能报告(Energe/Efficiency Performance Certificate) EPC (Energe/Efficiency Performance Certificate) 是英国房子的节能报告, 法律上规定, 每个房子都必须要有一个EPC报告, 报告的有效期为十年. 房东在把房子出租或者想卖房的时候, 这个EPC就必须有效, 在一些情况下 比如出租房子的时候, 这个EPC报告还必须符合一些最低标准, 比如房子必须满足 F档(类似及格线)...
- 给孩子零花钱培养孩子正确的金钱观价值观 两个娃已经不知不觉7岁8岁了. 媳妇和我商量一下决定给孩子每人每周5英镑的零花钱(Pocket Money). 这样他们慢慢的就有自己的小积蓄备将来不时之需: 比如朋友聚会生日啥的需要准备礼物. 同时, 我们决定不再给孩子买零食(薯片啥的). 孩子一天好几餐, 晚上睡觉前还得吃零食, 我们就多买了很多水果面包, 健康的食物多吃一些总不是啥坏事. 孩子可以用这些零钱买自己想要的东西, 我们也不再过问. 孩子有自己的决定权. 第一周的时候,...
- 拔牙后的注意事项(图, 慎入) Care of Mouth after Extraction 昨天又拔了两颗牙, 初步定在5月4号装牙套. 这是牙医诊所给的术后注意事项: 拔完后需要等3-4小时麻醉失效后才能吃喝. 稍微流点血是很正常的. 但是请不要漱口吐出, 因为这会加速流血. 你只要轻轻的含着口水并咽下即可. 如果一直流血, 请拿着纱布(并不是纸巾)放在拔牙处20分钟. 24小时内请不要运动, 术后几小时内回家静静坐着. 12小时内不要吸烟, 喝酒或者喝热饮, 因为这会让伤口流血....
- 同一台服务器上多个WORDPRESS站点的一些设置可以移出去 我自从把所有网站都挪到一处VPS服务器上 就发现很多事情省事很多 可以同时管理多个网站 包括 WORDPRESS博客. 比如我有四个WORDPRESS博客 然后我就把通用的一些资料给移出去 移到 HTTP或者HTTPS都不能直接访问的文件夹里这样就更安全许多. 文件 wp-conn.php 存储了 相同的数据库资料. 1 2...
- ChatGPT-4 使用 Math Wolfram 插件解决数学脑筋急转弯问题 这篇文章, 我们看一个简单的数学问题(脑筋急转弯), 并用 Python 解决它. 我们看一下LLM(大型语言模型): ChatGPT3.5和ChatGPT4. 通过 ChatGPT-Plus 订阅(目前每月 20 美元 + VAT增值税), 我们可以启用...
- HPZ800服务器主板太老不支持超过2TB的大硬盘 我家里一直用的是HPZ800服务器, 很吵, 很老, 虽然这台服务器已经有十年之久(我在EBAY上买来用了五年多了), 但是即使放到今天, 这服务器速度依旧很快, 很稳定. 由于服务器用的是ECC较验内存, 所以基本上不重启关机. HPZ800主机有两个硬核CPU – 因特志强 X5650 – 每个CPU是12核....
