Python中简单取模与幂函数的Big-O复杂度是否正确？

问题背景 #

我实现了以下两个Python函数：

def modulo(a, b):
    """接收数字a和b，计算a % b。"""
    if b <= 0:
        return None
    div = int(a / b)
    return a - div*b

def power(a, b):
    """接收数字a和非负整数b，计算a**b。"""
    if b == 0:
        return 1
    else:
        return a * power(a, b - 1)

针对modulo函数，我不确定它的Big-O复杂度是否为O(a / b)——因为看起来执行耗时依赖输入a和b，但我在网上看到取模运算的Big-O复杂度为O(logn)，不确定是否适用于这个实现。另外，power函数的Big-O复杂度是否为O(a^b)？因为该函数涉及幂运算。

解答 #

1. modulo函数的时间复杂度 #

你的这个自定义modulo函数的时间复杂度不是O(a/b)，而是O(1)（常数时间）。

原因很简单：函数里的核心操作int(a / b)是Python底层通过优化的硬件算术指令实现的，它不是通过循环反复减b来计算商的——那种朴素的模拟除法算法才会有O(a/b)的复杂度。而Python的整数除法是高效的硬件级操作，不管a和b的常规大小如何，执行时间都是固定的（极端超大整数场景除外，但常规复杂度分析不考虑这种特殊情况）。

至于你看到的"取模运算复杂度为O(logn)"，通常指的是不依赖硬件除法指令的模拟实现（比如用二进制分解思路实现的取模算法，类似快速模幂的逻辑），这种场景下复杂度是O(logn)，但和你当前的实现完全无关，因为你直接用了Python内置的除法操作。

2. power函数的时间复杂度 #

power函数的时间复杂度不是O(a^b)，而是O(b)（线性时间）。

时间复杂度衡量的是算法执行的操作次数，而非返回结果的数值规模。你的递归实现中，每次递归都会让b减1，直到b等于0为止，总共会执行b次递归调用，每次调用仅做一次乘法操作（O(1)），所以总操作次数是b次，对应复杂度O(b)。

而O(a^b)是这个函数返回结果的数值大小，和算法的时间复杂度完全不是一个概念——比如当a=2，b=10时，结果是1024，但算法只执行了10次乘法，而非1024次操作。

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