简单 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

答案说它的O(n(。

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

for k in range(i,i)

for循环永远不会执行。

所以，你的代码等效于

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( 次，然后从函数返回。

因此，总复杂性O(sqrt(n) * sqrt(n))这是O(n)