了解此python函数的运行时

Question

def loopy_loop(n):
  for i in range(n):
    for j in range(i):
      if j*j > i:
        break

其中n是正整数。你知道吗

假设我取n=10

外循环肯定会运行n次（n=10次） 内部循环将基于这些值运行。你知道吗

• n=0，内环运行0次

• n=1，内部循环运行一次

• n=2，内环运行3次

• n=3，内部循环运行4次（直到j=3，9>；3）

• n=4，内部循环也运行4次

• 以此类推，直到n=9，它将运行5次

我很难把所有的东西放在一起，用big O表示法来表示运行时。有没有一套算法可以帮助我处理这个特定的代码片段？你知道吗

Answer 1

外循环运行n次。你知道吗

内环运行sqrt(i)次（因为当i给定时，当j**2到达i时它停止），但i增长（大致）类似于n（n//2平均值）

复杂性是O(n**1.5)（n乘以n的平方根）

更准确的估计：

def loopy_loop(n):
    counter=0
    for i in range(n):
        for j in range(i):
            counter+=1
            if j*j > i:
                break
    return counter,int((n)*(n//2)**0.5)

print(loopy_loop(5))
print(loopy_loop(10))
print(loopy_loop(100))
print(loopy_loop(1000))
print(loopy_loop(15000))

结果（计数与估计）：

(10, 7)
(31, 22)
(810, 707)
(22579, 22360)
(1247250, 1299038)