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

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