循环中循环的大 O 表示法是什么

Question

我有这段代码，但无法理解其中的 Big-O...谢谢

for(i = 0; i<n; i++){
  for(j = i; j<n; j++){
    if (arr[j]%2!=0){
       if (minodd > arr[j]){
       }
    }
  }
}

Answer 1

~~这不是永远持续下去吗？~~

~~你的内循环中有 i < n，所以我认为它是 O(inf)。~~

既然你已经更新了循环，我认为 @e2-e4 是正确的：

#include <stdio.h>

int eqn(int n)
{
    return n > 0 ? n + eqn(n - 1) : 0;
}

int main(int argc, char **argv)
{
    int i, j, n, v, a;

    v = 0;
    n = 5;

    for (i = 0; i < n; i++) {
        for (j = i; j < n; j++) {
            v++;
        }
    }

    // v = 15 ? 15
    printf("v = %d ? %d\n", v, eqn(n));

    return 0;
}

Answer 2

解决此问题的最佳方法之一是将其分解为更小的部分。

首先，让我们看看您的内部循环：

for(j = i; j<n; j++){
    if (arr[j]%2!=0){    // O(1)
       if (minodd > arr[j]){ // O(1)
       }
    }
  }

if 语句是 O(1) 或常数时间，所以我们可以忽略它们，我们只得到内部 for 循环：

for(j = i; j<n; j++){
... // O(1) + O(1)
}

由于最坏的情况是它循环 n 次我们有 O(n) + O(1) + O(1) 可以简化为 O(n) 称为 线性时间.

接下来，让我们缩小并用我们的新信息替换内部循环：

for(i = 0; i<n; i++){
  for(j = i; j<n; j++){
    if (arr[j]%2!=0){
       if (minodd > arr[j]){
       }
    }
  }
}

变成：

for(i = 0; i<n; i++){
    O(n)
}

因为我们知道外部for循环在最坏情况下会循环n次，而内部for循环在最坏情况下会循环n次：我们得到O(n x n)或O(n²) 也称为 多项式时间.

循环中循环的大 O 表示法是什么

What is the Big O notation of a loop in loop

algorithm

big-o

for-loop