O(n ^ 2)复杂度

Question

以下哪一项具有O(n^2 )复杂性

public boolean findDuplicates(int[] inputData) {
        for (int i = 0; i < inputData.length; i++) {
            for (int j = 0; j < inputData.length; j++) {
                if (inputData[i] == inputData[j] && i != j) {
                    return true;
                }
            }
        }
        return false;
    }

VS

public boolean findDuplicates(int[] inputData) {
        for (int i = 0; i < inputData.length; i++) {
            for (int j = 0; j < inputData.length; j++) {
             System.out.println("...");
            }
        }
        return false;
    }

并if (inputData[i] == inputData[j] && i != j) { return true; }在第一回路打破的复杂性O(n^2),因为我看到,如果长度我将匹配只有2元件inputDate阵列是2.

如果这个菜鸟问题我很抱歉,但我不明白的是,复杂性是指迭代的总元素数还是满足条件的总数？

这个怎么样(假设我们不必计算确切的复杂性,并假设我们忽略了内部循环中的索引超出范围),这是

public boolean findDuplicates(int[] inputData) {
        for (int i = 0; i < inputData.length; i++) {
            for (int j = 1; j < inputData.length; j++) {
            ....
            }
        }
        return false;
    }

还在O(n^2)吗？

Answer 1

您发布的两种方法都具有O(n ^ 2)复杂度.第一个条件内的条件不会改变大O.