我无法找到以下函数的运行复杂性,因为这里连接了 3 个东西 1:输入大小 2:i 值 3:s 值。 请帮助我找到推理的运行复杂性。
def function(n):
i=s=1
while s<n:
i=i+1
s=s+i
print("*")
function(20)
最佳答案
这是O(sqrt(n))
算法。
The loop runs i times such that `1+2+..i<=n.`[maximum i]
or
i*(i+1)/2<=n or i^2/2<=n or i<=sqrt(2n)
~O(sqrt(n))
关于python - 有理由地运行以下功能的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33308535/