复杂性-在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)

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

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

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

然后，我们将来自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)成为最坏情况下的运行时。