小编zak*_*els的帖子

我试图找出函数的时间复杂度(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 …