가

Question

나는 최악의 경우 점근 적 복잡도를 결정하기 위해 다음과 같은 기능 싶습니다 첫째

int j; 
float r = 1.0; 
for (int i=1; i<(log n); i++){ 
    j = 1; 
    while (j <= i^2){ 
     r*=2; 
     j++; 
} 
print(r); 

Answer 1

을, 나는 가정합니다 코드에서 i^2은 "i bitwise-XOR 2"가 아닌 "i"이 C++ 구문과 일치하지만 예측할 수없는 결과를 생성하기 때문에 "2의 거듭 제곱으로 생성되었습니다"를 의미합니다. http://www.trans4mind.com/personal_development/mathematics/series/sumGeneralPowersNaturalNumbers.htm :

시간 복잡성 합 우리는이 웹 페이지에서 정보를 사용하여, 2의 힘에 자연수의 합을 평가해야

에 의해 주어진다.

은 그래서 시간 복잡도는