具有嵌套 for 循环的 java 代码的复杂性

Question

我正在尝试分析下面的这段代码。我希望计算复杂性和操作/迭代次数（这会导致复杂性）。我的猜测是复杂度为 O(n^2)，因为我嵌套了 for 循环。但是，在内循环中，值正在切换，替换位置。这个操作不会使算法重复多次，因此它超过 O(n^2)，还是只有 while 循环才有可能？我如何找到完成的迭代/操作的确切数量？

for (int i = 0; i < b.Length; i++)
{
   for (int j = i + 1; j < b.Length; j++)
   {
       if (b[i] > b[j])
      {
            t = b[i];
            b[i] = b[j];
            b[j] = t;
      }
   }
}

Answer 1

循环次数由b.length常量和索引变量i、j控制。只要你不在循环中干预 i 和 j，复杂度保持不变。

Answer 2

外循环有 b.length 次迭代。我们称之为 n.

内部循环有 n - i - 1 次迭代。

内循环总迭代次数为

(n - 1) + (n - 2) + ... + 1 = n * (n -1) / 2 = O(n^2).

内部循环的每次迭代都在不断地工作——最多 1 个条件 + 3 个赋值——所以总运行时间是 O(n^2)。

确切的操作次数取决于输入，因为输入决定了条件为真的次数。

具有嵌套 for 循环的 java 代码的复杂性

Complexity of java code with nested for loops

java

time-complexity