java - 代码复杂度 = n^2？

Question

以下代码的复杂度是多少：

int data[] = { /* some numbers here */ };
n = data.length;

int lessThanCounter = 0;
for (int i=0; i<n; i++)
    for (int j=n-1; j>i; j--)
        if (data[i]<data[j]) lessThanCounter++;

根据我的计算，它是 O(n^2) - 这是正确的吗？

Answer 1

当您的外部循环执行n时间时，第一个乘数是n.

内部循环执行n-1, n-2...0大致相当于(n-1)/2.

因此，这会执行n * (n-1)/2时间，因此取决于O(n^2)或O(n^2/2)取决于您正在学习的大 O 风格。

注意：我添加了这个O(n^2/2)以迎合许多教育机构，他们没有正确理解 Big Oh，因此希望他们的学生以这种方式评估冒泡排序的 Big-Oh。我为这个明显误导性的错误道歉。

NBB：如果不清楚O(n^2/2)是错误的，我在发布时就知道它是错误的。但是，如果您的老师希望您将其放在答案中，那就这样做。你不太可能在试图解释错误的原因上取得进展。

Answer 2

对，那是正确的。内部循环的主体n-1在外部循环的第一次迭代中执行次数，在n-2第二次迭代中执行次数，依此类推，直到迭代次数为n第 th 次迭代n-n = 0。所以它的n-1 + n-2 + ... + 0 = (n-1)*n/2 = (n^2-n)/2总执行次数，确实在O(n^2).

Answer 3

为了证明你的算法的运行时间是 O(n^2)，在第一个循环中

for(int i=0:i<n;i++)

我从 0 到 n 和第二个循环：

for(int j = n-1;j>i;j--)

j 从 n-1 到 i

和上data[i]的比较都是在恒定时间内执行的data[j]lessThanCounter++O(1)

因此你有这个总结：

 $\sum_0^{n}(\sum_{n-1}^{i})1$.

通过消除您获得的内部求和：i+n+2

你现在有 sum(i=0 to n-1) of (n+i+2)

然后 sum(i=0 to n-1) of (n+2) + sum(i=0 to n-1) of i = (n+1)*(n+2) + n(n+1)/ 2

这显然是 O(n^2)

希望能帮助到你！

Answer 4

你是绝对正确的，循环内循环是 O(n^2)