各反復で2倍になると、この時間の複雑さはどうなりますか？

Question

int i = 1; 
while(i < N) { 
    i *= 2; 
} 

私たちは1,2,4,8,16 ...（Squares）を訪問しているので、私は大規模な時間の複雑さはO（log n）であるべきだと思います。答えは正しいのですか？解決策に到着した方法は正しいですか？

Answer 1

はい、あなたの答えは正しいです。一般的に言えば、ある値が指数関数的に増加する場合、ある固定値を超える前に対数的に何度も行うことができます。