Tifa's Blog
·
随笔 - Miller-Rabin + Pollard-Rho 分解质因子的时间复杂度分析
💡
原文中文，约2800字，阅读约需7分钟。
📝
内容提要
本文探讨了质因数分解的算法，重点介绍了Miller-Rabin和Pollard-Rho算法，时间复杂度均为O(n^{1/4})。通过递归和回调函数分析了pfactors函数的复杂度，并利用Jensen不等式证明了其复杂度上界。
🎯
关键要点
- 本文探讨质因数分解的算法，重点介绍Miller-Rabin和Pollard-Rho算法。
- Miller-Rabin算法的时间复杂度为O(n^{1/4})。
- Pollard-Rho算法的期望时间复杂度为O(n^{1/4})。
- pfactors函数通过递归和回调函数分析其复杂度。
- 利用Jensen不等式证明pfactors函数的复杂度上界。
- pfactors函数的时间复杂度可表示为O(T(n))，并通过数学归纳法进行证明。
- Jensen不等式用于证明O(T(n))的复杂度上界。
🏷️
标签
➡️
