c - 表示为大O符号

Question

所以我明白，如果两个 while 循环只是 while (x < n)，那么它将表示为 O(n^2)，但是除以二，我如何将其放入我的方程中？谢谢

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

Answer 1

该程序片段实际上计算了数组元素的总和。 如果 n 是元素的数量，那么它会运行第一个循环 n/2 次和内部(第二个)循环 n/2 次，总共 n 次，因此，它是 O(n)。 让我们用一个例子来逐步解释: 说，

int arr[] = {10, 20, 30, 40, 50}; 
int n = 5;

以下是执行步骤:

1. (first loop) arr[0](10) is added, result becomes 10, x becomes 1
2. (first loop) arr[1](20) is added, result becomes 30, x becomes 2
3. (first loop) arr[2](30) is added, result becomes 60, x becomes 3
4. (first loop) arr[3](40) is added, result becomes 100, x becomes 4
5. (first loop) arr[4](50) is added, result becomes 150, x becomes 5

因此，第一个循环执行了 Floor(n/2) 次，即 2 次(步骤 1, 2) 而在步骤 2 中，它运行第二个内部循环(x >= n/2 即 x>= 2)，第二个循环运行上限(n/2)，即 3 次(步骤 3、4、5)并且两个循环都运行结束 因此，总体时间复杂度为 O(n)。 但是，这可以做得更简单，例如:

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