c - 如何找到 while 循环的时间复杂度(Big O)？

Question

代码 1

int i = 0;
int j = 0;
while(i < n){
     while(j < n){
        printf("{%d,%d}",arr[i],arr[j]);
        j++;
    }
    i++;
    j = 0;
    printf("\n");
}

代码 2

int result = 0;
int i = 0;
while (i < n / 2){
    result += arr[i];
    i += 1;
    while (i >= n / 2 && i < n){
        result += arr[i];
        i += 1;
    }
}
printf("%d\n", result);

我只知道如何用for循环求时间复杂度，但我不确定while循环。如果有人能帮我找出每个代码的总运行时间，将不胜感激。

Answer 1

归根结底，for 循环是 while 循环。形式的东西:

for(int i=0; i<n; i++)

相当于:

int i=0;

while(i<n)
{
 i++;
}

事实上，在算法的纯数学分析中，您应该在算法中将任何 for 循环变成 while 循环(原因有几个)。

回到你的代码。分析很简单:

• 在 while 循环的第一次迭代之前，i 的值为 0。
• 存在更新变量 i (i++) 的唯一语句。
• 在外循环的每次迭代中，i 增加 1。

• 外层循环最多运行n次。

• 在任何循环迭代之前，j 的值为 0。

• 有 2 个更新 j 的语句(j=0 和 j++)

• 非正式地:我们可以在内部循环的任何迭代之前告知 j 的值为 0。

• 在内循环中，更新 j 的唯一语句是 j++。

• 在内循环的每次迭代中，j 增加 1。

• 内部循环最多由循环守卫运行 n 次。

• 外循环最多运行n次，内循环最多运行n次外循环的每次迭代。所有其他陈述都是不变的。算法在O(n*n)=O(n^2)

第二个稍微复杂一些但是:

• 在外循环的第一次迭代之前，i 的值为 0。
• 通俗地说:外层循环会一直运行到 i 的值为 (n/2 - 1)
• 更新语句(i += 1)将i更新为(n/2)
• 通俗地说:内部循环运行 (n-n/2 = n/2) 次，并且恰好运行一次。- 外层循环运行 n/2 次，内层循环运行 n/2 次恰好一次。

算法因此运行 O(n/2+n/2) = O(n) 次