python - 简单Python程序的时间复杂度

Question

def foo(n):
    for i in range(n):
        for k in range(1,i):
            if k>n/k:
                return k

这个程序的时间复杂度是多少？ 答案是 O(n)。欢迎对此进行任何解释

编辑:拼写错误

Answer 1

answer says its O(n).

是的，复杂度是O(N)，因为

for k in range(i,i)

for loop 永远不会执行。

所以，你的代码相当于

def foo(n):
    for i in range(n):
       pass

更新

def foo(n):
    for i in range(n):
        for k in range(1,i):
            if k>n/k:
                return k

k>n/k 相当于 k^2 > n 并且它是 k > sqrt(n)

主循环主要执行sqrt(n)次，内部循环执行0次 ，然后1次，然后2次，.....，sqrt(n)次，然后从函数返回。 p>

因此，总复杂度为O(sqrt(n) * sqrt(n))，即O(n)