渐近增长率 “INT I =常量1;而（ⅰ<N）{I * = CONSTANT2;}”

Question

什么是这个函数的渐近增长率：

int i=3; 
while(i < n) { 
    i *= 5; 
} 

我测量它：

当n=3i<n执行1次

。 。

当n=16i<n被执行2次

。 。

时n=80，i<n被执行3次

。 。

我需要找到正确的增长率，但我卡住了。

Answer 1

我认为增长速度是：

3 * 5^x >= n 
5^x >= n/3 

因此

xlog5 >= log n - log 3 
x >= (log n - log 3)/(log 5) 

可以定义3*5^x必须>=n。我们可以用这个基础在第一行中设置方程。