函数的时间复杂度

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

首先，对于第一个函数，时间复杂度似乎更接近 O(N log N)，因为每个循环的参数每次都会减少。

此外，对于第二个函数，运行时间为 O(log2 N)。例外的是，假设 i == n == 2。一次运行后 i 为 1。另一次运行后 i 为 0.5。再过一会我就是0.25。依此类推...我假设您需要 int(i)。

要了解每个函数的严格数学方法，您可以访问https://www.coursera.org/course/algo。对于此类事情来说，这是一门很棒的课程。我的计算有点马虎。