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

对比

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) 的复杂性，如我所见，如果 inputDate 数组的长度为 2，我将仅匹配 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。