确定Big-O复杂性

Question

我下面有一些代码，其中包含一个嵌套的while循环。我估计了外部while循环的复杂性，但我不确定如何处理内部循环，因为它有一个&&。有人能给我解释一下如何确定内循环的复杂度吗？

int result = 0;
int i = 0;
while (i < n / 2){                // O(log N)
    result += arr[i];
    i += 1;
    while (i >= n / 2 && i < n){  //Not sure how the parameters change it. O(log N) ? 
        result += arr[i];
        i += 1;
    }
}
printf("%d\n", result);

Answer 1

外部循环递增，直到i= (n / 2) - 1。下一个i += 1将其置于i= n /2，然后内部循环运行，直到i=n。外部循环不会进行另一次迭代。

以下内容将是等效的。

while (i < n / 2){
    result += arr[i];
    i += 1;    
}
// i = n / 2
while (i < n){
    result += arr[i];
    i += 1;
}

O(n) + O(n) = O(n)

Answer 2

下面是编写代码的另一种方式：

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

所以它显然是O(n)，或者说线性时间。