计算以下代码的时间复杂度

Question

有人可以帮助找出以下代码的复杂性吗？

def mystery(n):
    sum = 0
    if n % 2 == 0:
        for i in range(len(n + 10000)): 
            sum += 1

    elif n % 3 == 0:
        i, j = 0, 0
        while i <= n:
            while j <= n:
                sum += j - 1
                j += 1
            i += 1
    else:
        sum = n**3

下面代码的时间复杂度会不会是O(n^2)，因为在最坏的情况下，elif语句会被执行，所以外层的while循环会执行n次，而嵌套的while循环会是执行 n 次一次只是因为我们从未重置 j？因此，我们将有 O(n^2 + n) 并且因为首项是 n^2，复杂度将是 O(n^2)?

Answer 1

在 elif 部分：

当i=0时，while j <= n:循环是O(n)。
当i>0时，j=n+1，所以while j <= n:循环是O(1)。

所以 elif 部分是 O(n) + O(n*1) = O(n+n) = O(n)。

计算以下代码的时间复杂度

Calculating the time complexity of the following code

python

big-o

time-complexity