java - 为什么数组比 ArrayList 快这么多？

Question

最近，我试图解决Problem 23 of Project Euler .为此，我首先创建了一个包含所有丰富数字的列表，称为 abundants。

接下来，我遍历此列表并构建另一个列表，其中包含低于某个限制的丰富数字的所有总和。现在我注意到了一些奇怪的事情。我使用嵌套循环在列表中迭代两次。但是，如果我使用数组来存储总和，则需要几秒钟，如果我将总和添加到 ArrayList 中，则需要数小时。这是什么原因？我认为代价高昂的操作是两个嵌套循环，但似乎代价高昂的操作是 ArrayList#add。任何提示为什么会这样？

这里是数组的代码:

for (int i = 0; i < abundants.size(); i++) {
   for (int j = 0; j < abundants.size(); j++) {
      int tot = abundants.get(i) + abundants.get(j);
      if (tot <= limit)
         isSum[tot] = true;
      }
   }
}

这里是 ArrayList 的代码:

ArrayList<Integer> sums = new ArrayList<Integer>();
for (int i = 0; i < abundants.size(); i++) {
   for (int j = 0; j < abundants.size(); j++) {
      int s = abundants.get(i) + abundants.get(j);
      if (!sums.contains(s) && s < limit) {
         sums.add(s);
      }
   }
 }

Answer 1

您的 ArrayList 实现是 O(n^3) 而另一个是 O(n^2):sums.contains(...) 必须遍历整个 sums 列出你内循环的每次迭代。