この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回実行する

• など、それは5回

私は困難がランダウの記号を使用してランタイムを表現するために、一緒にすべてを入れて持っていますが実行されますN = 9、まで。この特定のコードスニペットで他のコードスニペットを助けることができるアルゴリズムが設定されていますか？

Answer 1

外側ループはn回実行されます。

（iが与えられたときj**2がiに達したときに停止するため）内部ループはsqrt(i)回実行されますがiは（おおよそ）n（n//2平均）のような成長

複雑さはnのO(n**1.5)（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)