알고리즘 : k와 n의 관계는 무엇입니까?

Question

은^(n)의 값을 계산하기 :

방법 항목 : 방법 2를 사용하여 개선 된 경우

가

result = 1; 
    for(int i = 1; i <=n; i++) 
     result *= a; 

:

result = a; 
for(int i = 1; i <=k; i++) 
    result = result * result; 

방법 I는 K 및 N의 관계를 추론 할 수 있을까? 그리고 왜? 감사합니다.

Answer 1

첫 번째 경우 결과 = a^n, 두 번째 경우 결과 = a^(2^k)이므로 2^k = n 및 k = logn입니다. 물론 이것은 2의 거듭 제곱 인 n에 대해서만 정확합니다.

Answer 2

당신은 exponentiation by squaring을하려고합니다.

분명히, 2의 거듭 제곱에 대해 k = log_2 n.

Answer 3

나는 첫 번째 경우에 a, a^2, a^3.a^n 이 두 번째 경우에^2, a^4, A^8 ...... A^(2^k)