如何为循环中增加不同的两个变量计算 O(n)？

Question

我尝试了很多方法并创建了 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

Answer 1

你的语句循环重复直到 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

如何为循环中增加不同的两个变量计算 O(n)？

How to calculate O(n) for two variables that increases differently in loop?

algorithm

input

data-structures

execution-time