python之如何计算嵌套 'for' 循环的时间复杂度

考虑:

def fun(n): 
 
    for i in range(1, n+1): 
        for j in range(1, n, i): 
            print (i, “,”, j) 

我在使用嵌套的 for 循环时遇到问题。是 2n^2 + 2n + 1 吗？

请您参考如下方法:

内部循环从 1(含)到 n(不含)，跳数为 i。因此，这意味着它将执行 (n-1)//i 步。

外循环使 n 运行，其中 i 的范围从 1 到 n。我们可以通过将步数计算为总和来稍微高估总步数:

 n                    n 
---                  --- 
\     n-1            \    1 
/     ---    = n-1 * /   --- 
---    i             ---  i 
i=1                  i=1 

我们可以在这里使用 Stirling 近似:我们知道积分 if 1/i 将介于 1/(i+1) 和 1/i.

1/i 的积分，因此我们将其近似为:

 n         n 
---        /\ 
\    1     |    1 
/   ---  ≈ |   --- dx  = log(n) - log(1) 
---  i    \/    x 
i=1        1

所以这意味着总步数是大 oh O(n log n)。