复杂性——在 C 语言中，这个算法的最佳和最差情况是什么？

Question

在这个算法中，N趋于无穷大（渐近分析）。在哪些情况下会导致最好和最坏的情况？

int i=1;
while(i < N)
  i = i + 3;
if(B[6] < 100)
  for(int j=1; j<N/2; j++){
    int k=j+1;
    while((k<N) && (k > j)){
      printf("%d", B[k]);
      k++
    }
  }

我发现了什么：最好的情况 O(N) 最坏情况：O(N^2) 是正确的？为什么？

这是一道数据结构题。

Answer 1

*我误读了最初的问题并编辑了我的答案

首先我会尝试稍微简化代码。

我们知道在表达式(k < N) && (k > j)中，k总是大于j，因为它被初始化为j+1，我们忽略溢出。

这给了我们：

int i = 1;
while(i < N) // O(N)
  i = i + 3; // O(1)

if(B[6] < 300) // Only consider what's inside in the worst case
  for(int j = 1; j < N / 2; j++) // O(N)
    int k = j + 1;               // O(1)
    while(k < N)                 // O(N)
      printf("%d", B[k]);        // O(1)
      k++;                       // O(1)

如果我们不进入 if 语句，我们在 while(i < N) 循环内执行 O(N) 工作并在其中执行恒定时间工作 (O(1))。然后我们乘以 N * 1 仍然得到 O(N)

这为我们提供了 O(N) 的最佳运行时间。

现在，对于最坏的情况，假设我们也进入了 if 语句。这意味着我们执行执行 O(N/2) 工作的 for 循环，它仍然是 O(N)。在 for 循环内部是另一个执行 O(N) 工作的 while 循环。

然后我们从 for(int j = 1; j < N / 2; j++) 乘以 O(N) 并从 while(k < N) 乘以 O(N) 因为它们是嵌套的并得到 O(N^2).

然后我们添加初始 O(N) 和 O(N^2) 得到 O(N^2 + N) 这实际上只是 O(N^2) 因为我们只关心最高缩放项。这使得 O(N^2) 成为最坏情况下的运行时间。

复杂性——在 C 语言中，这个算法的最佳和最差情况是什么？

Complexity - which is the best and worst case in this algorithm in C?

data-structures