Java

Question

我正在练习 Codility。有一个简单级别的问题，但我坚持表现。测试结果分析将这段代码标记为O(N**2)，但显然没有任何嵌套循环。谁能告诉我为什么我的代码是 O(N**2)？

public static int solution(int X, int[] A) {
    List<Integer> temp = new ArrayList<>();
    for (int i = 1; i <= X; i++ ){
        temp.add(i);
    }

    int counter = 0;
    int res = -1;
    for (int i: A){
        if (temp.contains(i)) {
            temp.remove(new Integer(i));
        }
        if (temp.size() == 0){
            res= counter;
            break;
        }
        counter++;
    }

    if (temp.size() != 0){

        res = -1;
    }
    return res;
}

Answer 1

另一个循环隐藏在ArrayList的remove方法中。 ArrayList 的 remove 方法是 O(N) 因为它必须移动元素来填充间隙。

for (int i: A){   // ===> O(N)
        if (temp.contains(i)) {
            temp.remove(new Integer(i));  //===> O(N)
        }
        if (temp.size() == 0){
            res= counter;
            break;
        }
        counter++;
    }

Answer 2

那是因为使用了contains。 temp 是一个 ArrayList，contains 执行线性查找。在 for 循环中，这将变为 O(N²).

Answer 3

The test result analysis marks this code as O(N**2), but obviously there are not any nested loops. Can anyone tell me why my code is O(N**2)?

渐近复杂性不（仅）与循环计数有关。您对 A 的元素进行循环，并在其中调用 temp.contains()，并有条件地调用 temp.remove()。对于 ArrayList，其中每个的成本与 temp 中的元素数量成正比。

总的来说，如果 N 是 A.length 那么你的方法的渐近复杂度是 O(X * N)。 Codility 的分析似乎不太正确，但如果 X 不能被视为受常数限制，那么您的代码仍然比 O(N) 更复杂。如果 Codility 执行的启发式分析在 X 和 N 之间引入了人为关系，那么 服从该函数关系 ，您的方法确实可能是 O(N²).

你绝对可以做得更好。您的方法似乎正在计算 A 的最小初始子数组的长度，其中包含 1 到 X 之间的所有整数。为了有效地做到这一点，您确实需要某种机制来跟踪已经看到的值，但是包含在 List 中是一个昂贵的选择。考虑使用 boolean 的数组来跟踪哪些特定值已被看到，以及已被看到的数量的单独计数：

boolean[] seen = new boolean[X + 1];
int numSeen = 0;

有了它，遍历 A 的元素，并且对于范围 1 ... X 中的每个元素 i，测试 seen[i]（成本 O (1) 每次测试）。如果 true，什么都不做。如果false，设置seen[i]为true（O(1)），递增numSeen（O(1)），测试numSeen是否达到X （O（1））。 Return 在 numSeen 达到 X 之前必须检查的元素数，如果 numSeen 从未达到 X，则为 -1。（细节留作练习。）

因此，无论 X 上的任何限制，每个循环迭代都会执行 O(1) 工作，而 O(1) 工作实际上便宜，这是一个不同的考虑。总的来说：O(N)，而且效率也很高。

Java - 时间复杂度 O(N**2)

Java - Time Complexity O(N**2)

time-complexity