다음 코드의 실행 시간은 얼마나됩니까?

Question

실행 시간은 단순히 n-i가 아니며 단지 O (n)입니까? 아니면이 상황에서 모든 것을 고려하지 않습니까?

i <- c 
while i < n do 
i <- i*c 
end while 

Answer 1

n에서부터 c의 대수와 로그가 같지 않습니까?

기본적으로 n의 값에 도달 할 때까지 i를 곱합니다.

Answer 2

이 알고리즘의 실행 시간은 O (log n)입니다. 값을 더하거나 뺄 때 루프 카운터를 증가시키지 않으므로 n-i가되지 않습니다. 오히려 루프 카운터를 c만큼 증가 시켜서 모든 반복에서 c로 스케일링합니다. 따라서 반복 할 수있는 최대 반복 수는 log_c (n)입니다.