下面代码的时间复杂度是多少？ [已关闭]

Question

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;
    }
}

我编写了这段代码来获取数字的所有除数，为此我使用了 Arraylist 来存储所有除数，然后使用 Collections.sort(list) 对列表进行排序。我还在努力学习如何回答代码的时间复杂度。代码的时间复杂度是多少？

Answer 1

问题的根源远比乍一看显而易见的多。我希望比老狗程序员（ODP）拥有更好数学技能的人可以在 ODP 失败的部分编辑这个答案，或者提供一个单独但更好的答案。

如果测量

for

循环的迭代次数，则循环将以

n^0.5

迭代运行。即“分数幂”时间， 或 O(n^c), 0 < c < 1，可表示为 O(n^(1/c)), 1 < c。

在这种情况下，循环内的操作并没有真正改变这一点。每次迭代最多将有这些操作：

• 两个部分：(a) 检查

  i

  是否是

  n

  的因子，(b) 检查找出因子对中的另一个因子。
• 两次致电

  list.add(int)

  。

无论哪种情况，这都会使它看起来像 O(2n^0.5)。但是，

2

不算数。因此，循环仍然具有 O(n^c), 0 < c < 1 复杂度。

接下来，考虑

Collections.sort (list)

。

Collections.sort (List list)

使用比较排序，运行时间为 O(n log n)。

由于 O(n log n) 比小数指数时间更差，我们可能得出答案是 O(n log n)。

因此，通过将

for(int i=1;i<=n;i++)

更改为

for(int i=1;i<=Math.sqrt(n);i++)

并添加代码来查找因子对中的另一个因子，迭代次数显着减少。但是，这是有代价的：所需的输出是

n

按升序排列 的因素。所以，成本就是增加排序。

可以通过使用

for(int i=1;i<=n;i++)

并删除代码来查找一对中的另一个因子来消除排序。然后，它将在

O(n)

时间内运行，这比 O(n log n) 好得多，并且会按升序生成因子列表。

但是，等等！运行排序时，

list

没有

n

元素。它的含量小于

n

。那么，给定一个正整数

n

，

n

最多可以有多少个因子？

其数学计算超出了 ODP。但是，原始问题中的

for

循环不可能将多个

2 * Math.sqrt(n)

元素放入

list

中。让我们将其视为最坏的情况，尽管实际最坏的情况会更小。

因此，看起来排序将花费 O(2√n * log (2√n)) 比较。我们可以消除每个

2

，给出 O(√n log √n)。

简化的数学计算再次超出了 ODP 的范围。但是，通过绘制它，它看起来比分数功率时间稍差，而分数功率时间比线性时间好得多。