java - 有限 for 循环迭代的复杂性

Question

我有一个关于复杂性的简单问题。我在 Java 中有这段代码:

pairs是 HashMap包含 Integer作为键，它的频率为 Collection<Integer>作为一个值。所以:

pairs = new Hashmap<Integer number, Integer numberFrequency>() 

然后我想找到匹配的Pair (a,b)验证a + b == targetSum 。

for (int i = 0; i < pairs.getCapacity(); i++) { // Complexity : O(n)
    if (pairs.containsKey(targetSum - i) && targetSum - i == i) {
        for (int j = 1; j < pairs.get(targetSum - i); j++) {
            collection.add(new MatchingPair(targetSum - i, i));
        }
    }
}

我知道第一个For循环的复杂度是O(n)，但是第二个for循环只循环了很少的次数，也就是数字-1的频率，我们还算O(n)吗(n) 所以这整个代码部分将是 O(n^2) ？如果是的话，有人有什么选择可以让它变成 O(n) 吗？

Answer 1

如果“pairs.getCapacity()”或“pairs.get(targetSum - i)”是您事先知道的常量，则其时间复杂度为 O(n)。否则，两个循环，一个嵌套在另一个循环中，通常是 O(n^2)。