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

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)。