与其他分解算法相比，时间复杂度 O(2^(n/2)) 的 n 位数字的整数分解算法的效率如何？
最佳答案
是的，从区间 [1..sqrt(X)] 检查所有除数的简单算法具有相同的复杂度 O(2^(n/2))。
Pollard's rho算法的复杂度为 O(2^(n/4))。这是一个旧算法，易于实现，适用于不太长的整数。
但是现代数论有更高效的算法，例如General number field sieve或 Pollard-Strassen Algorithm .
您可以在 wiki list 阅读更多关于已知流行分解算法的信息
关于algorithm - 时间复杂度为 O(2^(n/2)) 的整数分解算法的效率如何？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45497882/