Python 3.8+ 的整数平方根 `math.isqrt()` 函数的时间复杂度

Question

我正在尝试分析Python 3.8+版本中默认整数平方根函数的时间复杂度，

math.isqrt()

在计算

n

时，我尝试将这个函数的时间复杂度理解为

res = math.isqrt(n)

的函数，其中

res

是我们想要的结果值，

n

是一个整数。

我相信一些复杂性可能来自Python如何进行算术以及作为一种动态类型语言，因此在尝试时可能需要注意一些舍入和缓冲区下溢/溢出在后续轮次计算中将

float

值转换回

int

，直到满足阈值精度值的停止条件。

如果有人研究过Python的整数平方根函数

math.isqrt

，我很高兴找到你对时间复杂度和空间复杂度的算法复杂性分析的看法（如果存在递归元素，这可能是相关的）或存储小数点后的浮点数以供将来计算）。

Answer 1

@JonSG 是对的，模块源代码中提供了算法的详细描述。 描述的一部分（@President James K. Polk 也指出）是迭代次数：

该算法非常简单。没有必要 每次迭代检查和纠正步骤，终止很简单：迭代次数是预先知道的（对于

floor(log2(log2(n)))

来说正是

n > 1

）。

对于最终的复杂性：由于此方法可能适用于非常大的整数，因此适当考虑算术运算的确切复杂性。看一下参考代码的循环：

# ...
for s in reversed(range(c.bit_length())): # c proportional to log(n)
    e = d
    d = c >> s
    a = (a << d - e - 1) + (n >> 2*c - e - d + 1) // a
# ...

这里的瓶颈操作是除法

// a

，当使用 Havey-Hoeven 乘法算法 + Newton-Raphson 除法时 会导致除法复杂度为 O(b log(b))，其中 b 是位数，或相对于 n 作为一个值（如问题中所示）然后 O(log(n) log(log(n)))。 Python 使用的确切除法算法可能有所不同，但如果我们用这些选择重新实现算法，最终的复杂度为 O(log(n) log^2(log(n)))。