python - 我的算法最坏情况下的运行时间是多少

Question

所以我知道我的算法运行时间为 O(n)，因为它只需循环列表一次，但我不知道如何计算最坏情况的运行时间。它仍然是线性的，因为无论如何它都是循环的吗？

 def find_duplicates(lst):
    duplist = []

    for i in range(0, len(lst)):

        if abs(lst[i]) == len(lst):
            element = -1
        else:
            element = lst[abs(lst[i])]
        if element > 0:
            lst[abs(lst[i])] = -lst[abs(lst[i])]
        elif element == 0:
            lst[abs(lst[i])] = -len(lst)
        else:
            if abs(lst[i]) == len(lst):
                duplist.append(0)
            else:
                duplist.append(abs(lst[i]))

    return duplist

Answer 1

是的，确实是 O(n)。在最坏的情况下，所有 if 都将失败，并且每个 if block 的最后一条语句将被执行。因此，每次迭代执行 6 条语句。尽管如此，你的时间复杂度仍然是 O(6n)，仍然是 O(n)。