Python list.pop(i) временная сложность?

Ваш алгоритм действительно занимает O (n) времени, а алгоритм «всплывания в обратном порядке» действительно занимает O (n²) времени. Однако LeetCode не сообщает, что ваша временная сложность лучше, чем 89% представлений; он сообщает, что ваше фактическое время работы лучше, чем 89% всех представлений. Фактическое время работы зависит от того, с какими входными данными тестируется алгоритм; не только размеры, но и количество дубликатов.

Это также зависит от того, как усредняется время выполнения нескольких тестовых случаев; если большинство тестовых случаев предназначены для небольших входных данных, где квадратичное решение быстрее, то квадратичное решение может выйти вперед в целом, даже если его временная сложность выше. @Heap Overflow также указывает в комментариях, что накладные расходы системы оценки LeetCode пропорционально велики и довольно изменчивы по сравнению со временем, необходимым для запуска алгоритмов, поэтому несоответствие может быть просто связано со случайным изменением этих накладных расходов.

Чтобы пролить свет на это, я измерил время работы с помощью timeit. На графике ниже показаны мои результаты; формы именно такие, какие вы ожидаете, учитывая временные сложности, а точка пересечения находится где-то между 8000 < n < 9000 на моей машине. Это основано на отсортированных списках, в которых каждый отдельный элемент появляется в среднем дважды. Код, который я использовал для генерации времени, приведен ниже.

Код времени:

def linear_solution(nums):
    left, right = 0, 0
    while right < len(nums)-1:
        if nums[right] != nums[right+1]:
            nums[left+1]=nums[right+1]
            left += 1
        right += 1
    return left + 1

def quadratic_solution(nums):
    prev_obj = []
    for i in range(len(nums)-1,-1,-1):
        if prev_obj == nums[i]:
            nums.pop(i)
        prev_obj = nums[i]
    return len(nums)

from random import randint
from timeit import timeit

def gen_list(n):
    max_n = n // 2
    return sorted(randint(0, max_n) for i in range(n))

# I used a step size of 1000 up to 15000, then a step size of 5000 up to 50000
step = 1000
max_n = 15000
reps = 100

print('n', 'linear time (ms)', 'quadratic time (ms)', sep='\t')
for n in range(step, max_n+1, step):
    # generate input lists
    lsts1 = [ gen_list(n) for i in range(reps) ]
    # copy the lists by value, since the algorithms will mutate them
    lsts2 = [ list(g) for g in lsts1 ]
    # use iterators to supply the input lists one-by-one to timeit
    iter1 = iter(lsts1)
    iter2 = iter(lsts2)
    t1 = timeit(lambda: linear_solution(next(iter1)), number=reps)
    t2 = timeit(lambda: quadratic_solution(next(iter2)), number=reps)
    # timeit reports the total time in seconds across all reps
    print(n, 1000*t1/reps, 1000*t2/reps, sep='\t')

Вывод состоит в том, что ваш алгоритм действительно быстрее, чем квадратичное решение для достаточно больших входных данных, но входные данные, которые LeetCode использует для измерения времени выполнения, недостаточно велики, чтобы преодолеть вариации в оценке накладных расходов, и тот факт, что среднее значение включает время, измеренное на меньших входных данных, где квадратичный алгоритм работает быстрее.

Просто потому, что решение не O (n), вы не можете предположить, что оно равно O (n ^ 2).

Это не совсем становится O (n ^ 2), потому что он использует pop в обратном порядке, что каждый раз уменьшает время, чтобы вытолкнуть, использование pop (i) в прямом порядке потребует больше времени, чем в обратном порядке, так как pop ищет изнаночной и в каждой петле убавляем количество элементов на спинке. Попробуйте то же самое решение в необратном порядке, запустите несколько раз, чтобы убедиться, вот увидите.

В любом случае, относительно того, почему его решение быстрее, у вас есть условие if с большим количеством переменных, он использовал только одну переменную prev_obj, использование обратного порядка позволяет делать это только с одной переменной. Таким образом, количество основных математических операций в вашем случае больше, поэтому при одинаковой сложности O (n) каждый из ваших n-циклов длиннее, чем его.

Просто посмотрите на свою переменную count, на каждой итерации ее значение равно left+1, вы можете вернуть left+1, просто удалив это, вы уменьшите количество count=count+1, которое вам нужно сделать.

Я только что опубликовал это решение, и оно на 76% быстрее.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        a=sorted(set(nums),key=lambda item:item)
        for i,v in enumerate(a):
            nums[i]=v
        return len(a)

и этот дает быстрее, чем 90%.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        a ={k:1 for k in nums} #<--- this is O(n)
        for i,v in enumerate(a.keys()): #<--- this is another O(n), but the length is small so O(m)
            nums[i]=v
        return len(a)

Вы можете сказать, что оба они больше, чем O (n), если вы посмотрите на цикл for, но, поскольку мы работаем с дубликатами членов, когда я перебираю сокращенные члены, в то время как ваш код перебирает все члены. Таким образом, время, необходимое для создания этого уникального набора/слова, меньше времени, необходимого вам для перебора этих дополнительных членов и проверки условий if, тогда мое решение может быть быстрее.