复杂嵌套循环的时间复杂度

Question

以下代码的时间复杂度是什么？

def func(n):
    for _ in range(n):
        if n == 4:
            for _ in range(n):
                <do something>

对于特定的输入（n = 4），它的复杂度是 O(n^2)，但对于其他所有输入，它的复杂度是 O(n)。在这种情况下，最坏的情况显然是 O(n^2)，但是我的老师说 O(n) 是正确的答案。如果“大O”表示的是最坏的情况，为什么不是 O(n^2) 呢？

另一个例子是：

def func2(n):
    for _ in range(n):
        if n%2 == 0:
            for _ in range(n):
                <do something>

我对这段代码的运行时间不是很确定。同样，最坏的情况是 O(n^2)。这次一半的输入都会导致最坏的情况。这样说的话，能否认为这段代码的运行时间是 O(n^2) 呢？

如果第一部分是 O(n)，第二部分是 O(n^2)，那么在选择“大O”表示法中真正的最坏情况时，有没有什么通用的规则呢？

Answer 1

更新

第一个情况是O(n)，因为即使当n=4时，复杂度是一个嵌套循环，范围是4，这样的循环总共会执行16次。对于其他所有的n值，它的复杂度都是O(n)。随着n的增大，n==4的情况不会再出现，所以复杂度不会随着n的增加而增加。

在第二种情况下，func2的一半调用涉及一个复杂度为O(n^2)的内部循环，这就是为什么整体复杂度是O(n^2)。随着n的增大，所需的时间也会以O(n^2)的速度增长。