Big O 표기법으로 표현하기

Question

두 개의 while 루프가 (x < n) 동안 O (n^2)로 표현되지만 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 번 수행하므로 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 

, 제 1 루프는 바닥에 대해 실행한다 (N/2) 배 (2 번, 즉 (n> 2), 즉 3 번 (단계 3, 4, 단계 1, 2) 동안 두 번째 내부 루프 (x> = n/2 ie x> = 2) 5) 및 루프 양 끝 모두 따라서 전체 시간 복잡도는 O (n)입니다. 그러나, 이것은 할 수 있었다 같은 간단한 :

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