python - 函数的时间复杂度

Question

我正在尝试找出函数的时间复杂度 (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 循环中发生了什么。

谁能详细解释一下两者的时间复杂度职能？谢谢!

Answer 1

对于这样一个简单的案例，您可以 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 是 O (1) 如果 r 有 O(log n) 位 ( model has words with log n bits )。

第二个循环更简单:i//= 2 是 i >>= 1。 n 有 Θ(log n) 数字，每次迭代都会丢弃一个二进制数字(右移)，因此整个循环是 Θ(log n) 如果我们假设 log(n) 位的 i >> 1 移位是 O(1) 操作(与在第一个示例中)。