합산 표기법을 사용하여 알고리즘을 증명하는 방법은 Θ (log n)입니까?

Question

한다고 가정 나는 다음과 같은 코드가 있습니다

int sum = 0; 
int val=128; 
for (int i=n; i>=1; i=i/2) { 
    for (int j=1; j<val; j++) { 
    sum ++; 
    } 
} 

방법이이 Θ 수학적으로 (로그 n) 인 것을 입증 할 것입니까?

내 일반적인 접근 방식은 합계 (시그마 표기법)를 사용하는 것이지만,이 경우 루프 변수를 선형 적으로 증가시키지 않습니다. 이것에 대한 좋은 접근 방법은 무엇입니까?

Answer 1

i의 값은 n, n/2, n/4, ..., 1입니다. 정수이므로 최종 조건은 1입니다. n이 2^k이라고 가정하면, 반복 횟수는 k이고, 이는 log n입니다. 따라서 상황은 변하지 않습니다. 특정 반복 횟수가있는 for입니다.

val이 상수이기 때문에 내부 루프는 단일 명령문으로 간주 될 수 있습니다.