以下代码的时间复杂度是多少？

Question

下面代码的复杂度好像应该是O(n^2)，但是是O(n)，怎么办？

void fun(int n, int arr[])
{
    int i = 0, j = 0;
    for(; i < n; ++i)
        while(j < n && arr[i] < arr[j])
            j++;
}

Answer 1

j 不会在外循环的每次迭代中重置为 0。因此，它运行到 n-1 仅一次，与 i 相同。所以你有两个 parallel/intermingled 迭代从 0 到（最多）n-1.

在每一步中，程序都会将 i 加一。当 i 达到 n 时程序终止。 "outer loop" 是运行 n 次。

还有一个关于j的"inner loop"。但它所做的只是增加 j 直到它达到 i （最多，有时它会减少）。 j 永远不会减少。所以那部分也是运行总共最多 n 次（不是 "outer loop" 的每次迭代 n 次）。

Answer 2

答案是O(n) 外循环运行 'n' 次，而内循环在所有迭代中仅运行一次 'n' 次，因为 j 的值永远不会重置为 0。因此答案是 O(n+n)=O(n).

Answer 3

让我们考虑最坏的情况，当while循环被执行到最大次数。次。最初：i=0，j=0 => while 循环不会被执行，因为 arr[0] = arr[0] 即 j=0。第二次迭代：i=1，j=0 => while 循环在最坏的情况下执行，即 j=1。第三次迭代：i=2，j=1 => while 循环在最坏的情况下再次执行，即 j=2。 ... 第 n 次迭代：i=n-1，j=n-2 => while 循环在最坏情况下再次执行，即 j=n-1.

所以，通过做这个练习，我们可以观察到每次 j = i-1 除了 i=0 和 j=0 或者我们可以说 while 循环只是运行与 for 循环并行，因此没有。 while 循环的执行次数等于没有。 for 循环的执行次数。因此 Order = O(n);

Answer 4

乍一看，时间复杂度似乎是O(n^2)，因为有两个循环。但是，请注意，变量 j 并未针对变量 i 的每个值进行初始化。

因此，内部j++最多执行n次。

i 循环也运行s n 次。

因此，整个过程运行进行了 O(n) 次。

请注意问题中给出的函数与以下函数之间的区别：

void fun(int n, int arr[])
               {
int i = 0, j = 0;
for(; i < n; ++i)
{
    j = 0;
    while(j < n && arr[i] < arr[j])
        j++;
}

}`

还不服气？

让我们假设传递的数组的元素按降序排列。我们干脆通过代码干运行 :

               Iteration 1 : i = 0, j = 0. arr[0] < arr[0] is false. So, the 
                             inner while loop breaks.
               Iteration 2: i =1, j = 0. arr[1] < arr[0] is true. j becomes 
               Iteration 3 : i = 1, j = 1. Condition false. We break. Note 
                            that j will remain 1 and is not reset back to 0.
               Iteration 4 : i = 2, j = 1. arr[2] < arr[1]. True. j = 2.
               Iteration 5 : i = 2, j = 2. Condition false. Break.
               Iteration 6 : i = 3, j = 2. arr[3] < arr[2]. True. j = 3.
               Iteration 7 : i = 3, j = 3. Condition false. Break.

如您所见，在这种情况下，内部 while 循环仅运行s 一次。因此，总迭代次数为 2 * N.

Answer 5

答案是O(n)因为'while'循环里面的测试条件失败了！

while(j < n && arr[i] < arr[j])

一开始，i=0，j=0，也就是说arr[i] = arr[j]，但是while循环测试条件说的是arr[i]<arr[j]，假设arr[0]<arr[0]

代码仅运行 for 循环 n 次。

最后的答案是 O(n) 而不是 O(n^2)

为了清楚起见，您可以查看这两个示例

示例 1：

#include <stdio.h>

int main()
{
    int i = 0, j = 0; 
    int n = 5;
    int arr[] = {6,7,8,9,10,11};
    for(; i < n; ++i) 
    { 
        printf("\nThis is for loop, its running 5 times\n");
         
        while(j < n && arr[i] < arr[j]){ 
            j++;
            printf("\nThis is while loop!\n");
        }
    };
    return 0;
}

输出是：

This is for loop, its running 5 times

This is for loop, its running 5 times

This is for loop, its running 5 times

This is for loop, its running 5 times

This is for loop, its running 5 times

在上面的输出中，我们找不到 'while' loop

中的打印语句

示例 2：

#include <stdio.h>

    int main()
    {
        int i = 0, j = 0; 
        int n = 5;
        int arr[] = {6,7,8,9,10,11};
        for(; i < n; ++i) 
        { 
            printf("\nThis is for loop, its running 5 times\n");
            
            while(j < n && arr[i] <= arr[j]){ 
                j++;
                printf("\nThis is while loop!\n");
            }
        };
        return 0;
    }

这里做了一个小小的改动 arr[i] <= arr[j]

使用'='

输出：

This is for loop, its running 5 times                                                                                                                                          
                                                                                                                                                                               
This is while loop!                                                                                                                                                            
                                                                                                                                                                               
This is while loop!                                                                                                                                                            
                                                                                                                                                                               
This is while loop!                                                                                                                                                            
                                                                                                                                                                               
This is while loop!                                                                                                                                                            
                                                                                                                                                                               
This is while loop!                                                                                                                                                            
                                                                                                                                                                               
This is for loop, its running 5 times                                                                                                                                          
                                                                                                                                                                               
This is for loop, its running 5 times                                                                                                                                          
                                                                                                                                                                               
This is for loop, its running 5 times                                                                                                                                          
                                                                                                                                                                               
This is for loop, its running 5 times

这里执行了while循环中的print语句，因为arr[i]=arr[j]， arr[0] = arr[0]

对于上面显示的'Example 2'，时间复杂度是O(n^2)

Answer 6

请注意，变量 j 并未针对变量 i 的每个值进行初始化。因此，内部 j++ 将最多执行 n 次。 i 循环也运行 n 次。所以，整个过程运行了 O(n) 次。

以下代码的时间复杂度是多少？

What is time complexity for the following code?

time-complexity