求以下获取数字所有约数的Java代码的时间复杂度

原代码 #

public class Solution{
    public static List<Integer> printDivisors(int n) {
        List<Integer> list = new ArrayList<>();
        for(int i=1;i<=Math.sqrt(n);i++){
            if(n%i==0){
                list.add(i);
                if(n/i !=i)
                {
                    list.add(n/i);
                }
            }
        }
        Collections.sort(list);
        return list;
    }
}

时间复杂度拆解分析 #

这段代码的时间开销由遍历找约数和排序约数列表两部分组成：

1. 遍历找约数的循环
   循环从i=1执行到i≤√n，总执行次数为O(√n)。循环内的取余判断、列表添加操作都是常数时间O(1)，因此这部分的时间复杂度为O(√n)。

2. 排序操作
   Java的Collections.sort()底层实现是TimSort，时间复杂度为O(m log m)，其中m是约数的数量。对于整数n，约数的最大数量不超过2√n（每个小于等于√n的约数对应一个大于等于√n的约数），代入后可得排序的时间复杂度为O(√n log √n)，简化后为O(√n log n)。

最终时间复杂度 #

由于O(√n log n)的增长速度快于O(√n)，因此代码的整体时间复杂度为**O(√n log n)**。

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