3 个 O(n) 操作连续嵌套，但总共仍然是 O(n^2) 的 Big O。为什么？

Question

问题：“使用以下符号评估平均值和最坏情况的复杂性：n = len(a)。”

def anagramme_list(a, b):
    # Time complexity : O(n^2) O(n^2)
    # Space complexity : ~O(n) (list made out of a string)

    res = False  # O(1) O(1)

    if len(a) == len(b):  # (cond O(1)) O(n^2) O(n^2)
        liste_b = list(b)  # O(n) O(n)
        res = True  # O(1) O(1)

        for i in a:  # (it: O(n)) O(n^2) O(n^2)
            if i in liste_b:  # (cond O(n)) O(n) O(n)
                liste_b.remove(i)  # O(n) O(n)
            else:  # O(1) O(1)
                res = False  # O(1) O(1)

    return res

我想说的是，在最坏的情况下，我们得到了 O(n^3)，因为 O(n) (liste_b.remove(i)) 中有一个操作是由 O(n) 中的条件触发的（如果i in liste_b) 本身嵌套在 O(n) 的循环中。不用说这个答案让我感到惊讶...... 谁能解释一下为什么 O(n) 中的嵌套操作不被视为“嵌套”在其父级中（“if i in liste_b”），以及在更广泛的层面上，如何处理此中的大 O 评估请问案件类型？

Answer 1

是 O(𝑛²) 而不是 O(𝑛³)。让我们通过删除

for i in a

循环包装器来减少这个问题。然后我们就有了

if..else

块。请注意，这里不再有循环嵌套，因为对于执行

liste_b.remove(i)

所需的每个 内部步骤，不会执行 i in liste_b

；相反，首先 

i in list_b

 被执行完成，然后（可能）

liste_b.remove(i)

 被执行 

once。所以这个if

块并不代表𝑛²动作，而是𝑛+𝑛动作，仍然是O(𝑛)。