如何为循环中增加不同的两个变量计算 O(n)?
How to calculate O(n) for two variables that increases differently in loop?
我尝试了很多方法并创建了 n,i,t 值 table.I 注意到 n=1 循环 0 次 returns,n=2 循环=1 次,n=3 或 4 loop=2 time, n=5,6 or 7 loop=3 ,n=8,9,10,11 loop=4 四次我发现这些值完全理解但我没有找到这个算法的解决方案 O(n) .
function func3(n)
i = 1;
t = 1;
while i < n do
i = i + t;
t = t + 1;
end while
你的语句循环重复直到 i < n
。
i
是什么? i
是自然数之和i=1+2+3+...x
。前x
个自然数之和的公式为S=(x(x+1))/2
。
您的循环表达式是 i < n
。这意味着 (x(x+1))/2 < n
。当我们解决不等式时,我们得到x<(-1+sqrt(1+8n))/2
。由于循环迭代次数为整数,因此迭代次数首先是 int 低于 max x
。
例如:
n = 1, x<0,823 => number of iterations is 0
n = 2, x<1,436 => number of iterations is 1
n = 11, x<4,164 => number of iterations is 4
我尝试了很多方法并创建了 n,i,t 值 table.I 注意到 n=1 循环 0 次 returns,n=2 循环=1 次,n=3 或 4 loop=2 time, n=5,6 or 7 loop=3 ,n=8,9,10,11 loop=4 四次我发现这些值完全理解但我没有找到这个算法的解决方案 O(n) .
function func3(n)
i = 1;
t = 1;
while i < n do
i = i + t;
t = t + 1;
end while
你的语句循环重复直到 i < n
。
i
是什么? i
是自然数之和i=1+2+3+...x
。前x
个自然数之和的公式为S=(x(x+1))/2
。
您的循环表达式是 i < n
。这意味着 (x(x+1))/2 < n
。当我们解决不等式时,我们得到x<(-1+sqrt(1+8n))/2
。由于循环迭代次数为整数,因此迭代次数首先是 int 低于 max x
。
例如:
n = 1, x<0,823 => number of iterations is 0
n = 2, x<1,436 => number of iterations is 1
n = 11, x<4,164 => number of iterations is 4