深入探讨o(√n)时间复杂度算法：leetcode因子查找问题
本文深入探讨leetcode一道求解正整数第k个因子的问题，并介绍一种O(√n)时间复杂度的解法，优化了传统的O(n)方法。
问题描述
给定两个正整数n和k，求n的升序排列因子列表中的第k个因子。若n少于k个因子，则返回-1。
传统O(n)解法
最直观的解法是遍历1到n，检查每个数是否为n的因子。代码如下：
def getkthfactorofn(n, k): result = 0 for i in range(1, n + 1): if n % i == 0: result += 1 if result == k: return i return -1
该方法的时间复杂度为O(n)，效率较低。
优化：利用因子对称性
n的因子具有对称性：如果i是n的因子，则n//i也是n的因子。 例如，81的因子为[1, 3, 9, 27, 81]，可以看出3和27，9和9是成对出现的。 只有当n是完全平方数时，根号n才会单独出现。
利用此特性，我们只需遍历到√n即可找到所有因子。
O(√n)解法
改进后的代码如下：
import math def getkthFactorOfN(n, k): i = 1 factors_asc = [] factors_desc = [] while i * i <= n: if n % i == 0: factors_asc.append(i) if i * i != n: #避免重复添加根号n factors_desc.insert(0, n // i) i += 1 factors = factors_asc + factors_desc if k <= len(factors): return factors[k - 1] else: return -1
代码首先初始化i=1，并创建两个列表factors_asc和factors_desc分别存储升序和降序的因子。循环条件i * i
在循环中，如果i是因子，则将其添加到factors_asc，并判断是否为完全平方数，如果不是，则将n // i添加到factors_desc的头部（保证降序）。
循环结束后，将两个列表合并，如果k小于等于因子总数，则返回第k个因子，否则返回-1。
时间复杂度分析
该方法的时间复杂度为O(√n)，因为循环次数最多为√n。 这显著优于O(n)方法，尤其在n值很大的情况下。
进一步优化
为了进一步优化，可以避免使用len()函数，预先计算因子数量，从而将时间复杂度降低为严格的O(√n)。
结论
本文介绍了利用因子对称性优化LeetCode因子查找问题的方法，将时间复杂度从O(n)降低到O(√n)，有效提高了算法效率。 该方法充分体现了算法设计中优化技巧的重要性。
*数学函数图像*
