python - 函数的时间复杂度

我试图找出函数的时间复杂度(Big-O)，并试图提供适当的理由。

第一个功能是:

r = 0
# Assignment is constant time. Executed once. O(1)
for i in range(n):
    for j in range(i+1,n):
        for k in range(i,j):
            r += 1
            # Assignment and access are O(1). Executed n^3

像这样。

我看到这是三层嵌套循环，因此它必须是O(n ^ 3)。
但我认为我的推理能力很弱。我真的不明白发生了什么
在这里的三重嵌套循环中

第二个功能是:

i = n
# Assignment is constant time. Executed once. O(1)
while i>0:
    k = 2 + 2
    i = i // 2
    # i is reduced by the equation above per iteration.
    # so the assignment and access which are O(1) is executed
    # log n times ??

我发现此算法为O(1)。但是像第一个功能一样
我看不到while循环中发生了什么。

有人可以彻底解释两者的时间复杂度吗
职能？谢谢!

最佳答案

对于这种简单的情况，您可以find the number of iterations of the innermost loop as a function of n exactly:

sum_(i=0)^(n-1)(sum_(j=i+1)^(n-1)(sum_(k=i)^(j-1) 1)) = 1/6 n (n^2-1)

即 Θ(n**3) 时间复杂度(see Big Theta):如果r += 1具有r数字(model has words with O(log n) bits)，则假定log n为O(1)。

第二个循环更简单:i //= 2是i >>= 1。 n具有Θ(log n)数字，并且每次迭代都丢弃一个二进制数字(向右移位)，因此，如果我们假设Θ(log n)数字的i >> 1移位是O(1)操作，则整个循环为 log(n) 时间复杂度(与第一个示例相同的模型) )。

关于python - 函数的时间复杂度，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/28572516/