模幂运算mod_exp的大O符号时间/空间复杂度解析请求

先明确核心前提：我们把指数y的二进制位数（记为k=log₂y）作为核心输入规模，同时假设N是固定或与y同规模的整数，其二进制位数记为m=log₂N。

逐行复杂度拆解 #

def mod_exp(x, y, N): 
    if y == 0:          # Time: O(1), Space: O(1)
            return 1
    z = mod_exp(x, y//2, N)         # Time: 对应处理y/2规模的递归时间；Space: 栈空间增加1层，最终总栈深度为O(log y)
    if y % 2 == 0:
        return (z**2) % N   # Time: O(m²)（或O(1)，若N为固定常数），Space: O(1)
    else:
        return (x*(z**2)) % N   # Time: O(m²)（或O(1)，若N为固定常数），Space: O(1)
#Total Time: O(log y * m²)；若N固定则为O(log y)；Total Space: O(log y)

关键细节解释 #

1. 基础情况（y==0）
   只是简单的条件判断和返回操作，无循环或复杂运算，时间、空间均为常数级O(1)。

2. 递归调用
   每次递归将指数y减半（y//2），递归深度为log₂y（比如y=1024时仅需递归10次就到y=0）。这意味着递归栈的空间复杂度为O(log y)——每一层递归都会在栈上保留一个栈帧，直到递归到基础情况才逐层返回。
   递归调用的时间是分治核心：每次仅处理一半规模的问题，总递归次数为log₂y次。

3. 返回语句中的平方与取模
   核心是大整数运算的复杂度：z是模N后的结果，大小不会超过N-1，二进制位数最多为m=log₂N。两个m位整数相乘（z²）用普通竖式乘法是O(m²)；若用Karatsuba等高效算法可降至O(m^1.585)，入门分析通常以O(m²)为准。
   取模运算（%N）的复杂度与乘法相当，本质是对乘积做除法取余，同样需要O(m²)时间。
   若N是固定大小的常数（比如仅处理561这类小卡迈克尔数），m为固定值，这部分运算时间可视为O(1)。

总复杂度总结 #

• 时间复杂度：
  • 若N固定：总时间为O(log y)——每次递归运算为常数级，共执行log y次递归。
  • 若N规模随y增长（如N与y同位数）：m≈log y，总时间为O((log y)³)——log y次递归，每次运算时间为O((log y)²)。
• 空间复杂度：
  始终为O(log y)，由递归栈深度决定，与N的大小无关。

你疑惑的点解答 #

• 为什么不是O(2ⁿ)：指数级复杂度出现在类似未优化的斐波那契递归场景，每次调用会衍生两个新递归，导致调用次数指数增长。而本函数每次递归仅调用一次，问题规模减半，递归次数为对数级，完全不会出现指数级复杂度。
• 返回语句的复杂度：既不是O(n)也不是O(2ⁿ)，而是与N的位数平方相关（O(m²)），若N固定则为O(1)。若n指y的数值，m=log N≈log y，也可表述为O((log n)²)。

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