如何找到 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)
• 非正式地说：内部循环运行 (nn/2 = n/2) 次，并且只运行一次。- 外循环运行 n/2 次，内循环运行 n/2 次，恰好一次。

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