c - 下面函数的时间复杂度是多少？

Question

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

给出的答案是:变量j并没有针对变量i的每个值进行初始化，所以时间复杂度为O(n)

我不太明白。谁能解释一下吗？

Answer 1

查看您的函数与此函数之间的差异(此函数的时间复杂度为 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++;
    }
}

在你的函数中变量 j未针对变量 i 的每个值进行初始化。因此，内部循环最多运行 n 次。

编辑 1- 来自 j=0至j=n最大n内部迭代while环形。因为你从未初始化j再来一次j=n内在while循环将永远不会迭代。因此，最多(可能会更少，具体取决于第二个条件 arr[i] < arr[j] )，您有 n内部迭代while循环一次。外层for循环显然会迭代 n次。所以你有n+n=2n而不是n 2 即使在最坏的情况下。

编辑 2- @Kerrek SB 对此的回答非常准确 -
“当j增加n次时，代码完成。j永远不会减少，最多n尝试增加它(通过i)”