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.

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

这个怎么样（假设我们不需要计算确切的复杂度，并且假设我们忽略了内循环中的 index out of bounds），这是

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.

Answer 2

大 O 表示法描述了当参数趋向于特定值或无穷大时函数的限制行为。

我想你很清楚第二种情况的时间复杂度为 O(n^2)。

在第一种情况下，除非你总能确保在前 k 次迭代中找到重复项，其中 k 是一个不依赖于 n 的常数，否则它的复杂度为 O(n) [由于 O(kn) 其中 k 是一个常数，无论多大，但已知，是 O(n)]

但是，如果这个 k 以任何方式依赖于 n（比如，你总是会在重复的数组的前半部分找到一个匹配项），或者不能保证每个运行都匹配，那么复杂度为 O(n^2)。 [O(n*n/k) = O(n^2) 其中 k 是常数。这里，k 是一个任意常数，它有助于找到在找到重复元素的第一个索引之前必须经过的数组百分比]

编辑：

之前没有注意到您的编辑。是的，第三种情况也是O(n^2) 你还可以做如下优化：

findDuplicates(int[] arr) {
    for (int i = 0; i < arr.size(); i++) {
        for (int j = i+1; j < arr.size(); j++) {
            ....
        }
    }
}

上面的例子也有O(n^2)的复杂度，因为它会经历n + n-1 + n-2 + .... + 1次循环，即(n *n+1/2)，也就是 O(n^2)

Answer 3

以上所有循环都是O(n^2)。
通常在最佳、平均和最坏情况下分析算法。

对于有条件的循环：最坏情况：O(n^2)
最好的情况：常数时间。因为最好的情况是 inputData[0]==inputData1

对于没有条件的循环：
现在，它变成了嵌套数组遍历，所以最坏和最好的情况都是 O(n^2).

总的来说，最坏情况下的性能用于评估算法，但很少有算法（例如 Quicksort）在平均情况下与最坏情况相比表现得非常好。

O(n^2) 复杂度

O(n^2) complexity

java

big-o