具有特殊内循环的大 O 表示法

Question

我想在分析以下大 O 符号方面得到一些帮助。

案例A： 内循环在最坏的情况下只运行一次

    for (int i = 0; i < nums.length; i++) {

       if (i==nums.length-1 && nums[i] == 3){
          for (int j = 0; j < nums.length; j++) {
           print();
          }
       }
    }

最坏的情况是数组以 3 结束。这是 O(N) 还是 O(N*N)？

我是这样分析的：

外层数组运行N次= 1(n)
最坏情况下的内循环只运行 1 次 = 1

所以，n*1 = O(n)，我可以分析吗？

“n*1”有意义还是应该是“n+1”？

案例B：

内循环总是运行，除非 i 是第一个元素

   for (int i = 0; i < nums.length; i++) {
     if (i!=0){
        for (int j = 0; j < nums.length; j++) {
          print();
        }
     }
   }

我的分析方法如下：

外层数组运行N次= n
内循环运行N -1次=n-1

所以，n*(n-1) = O(n*n)，我可以分析吗？

我对那些案例很困惑，谢谢！

Answer 1

案例A：

The outer array runs N times= 1(n)
The inner loop in the worst case runs just 1 time = 1

我认为你在这里的推理可能没问题，但正如它所写的那样，这不可能是正确的。 The outer array runs N times 意味着你计算 1 循环的每次迭代，但 The inner loop in the worst case runs just 1 time 不可能是正确的（在相同的定义下），因为它将有 n 迭代作为好吧（在最坏的情况下，即如果最后一个元素是 3）。我认为您在第一行使用了 runs = number of iterations，在第二行使用了 runs = starts/finishes；两者都没有问题，但请确保清晰一致。

你说得对 The worst case scenario is an array that finish in 3，在这种情况下它运行外循环 n 次（跳过内循环）然后在最后一次迭代中它不会跳过内部循环，运行 n 次。这是 O(n+n) = O(n).

另一种思考方式是代码可以重写为：

for (int i = 0; i < nums.length; i++) {
}

if ((nums.length > 0) && (nums[nums.length-1] == 3)){
    for (int j = 0; j < nums.length; j++) {
        print();
    }
}

我们为最坏的情况重写如下：

for (int i = 0; i < nums.length; i++) {
}

for (int j = 0; j < nums.length; j++) {
        print();
}

那么它的连续性就很明显了：n + n 工作。这里重要的是我们没有以任何重要的方式改变算法（我们没有影响最坏情况的复杂性）。

案例 B：

你的逻辑和数学看起来不错。

具有特殊内循环的大 O 表示法

Big O notation with special inner loop

algorithm

big-o

案例A：

案例 B：