什么是我的算法的最坏情况运行时间

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），因为无论满足哪些条件，它都会与输入列表的大小迭代完全相同的次数，没有额外的迭代嵌套在里面。

Answer 2

是的，它确实是O（n）。在最坏的情况下，所有if都将失败，并且每个if块的最后一个语句将被执行。因此，每次迭代都会执行6个语句。然而，你的时间复杂度将是O（6n），它仍然是O（n）。