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

Question

Я смотрю онлайн и знаю, что list.pop() имеет O (1) временную сложность, но list.pop(i) имеет O (n) временную сложность. Когда я пишу leetcode, многие люди используют pop(i) в a для l oop и говорят, что это O (n) сложность по времени, и на самом деле это быстрее, чем мой код, который использует только один l oop, но многие линии в этом l oop. Интересно, почему это произошло, и я должен использовать pop(i) вместо многих строк, чтобы избежать этого?

Пример: Leetcode 26. Удалить дубликаты из отсортированного массива

Мой код: (быстрее чем 75%)

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        left, right = 0, 0
        count = 1
        while right < len(nums)-1:
            if nums[right] == nums[right+1]:
                right += 1
            else:
                nums[left+1]=nums[right+1]
                left += 1
                right += 1
                count += 1
        return count

и код других людей, быстрее, чем 90%: (этот парень не говорит O (n), но почему O (n ^ 2) быстрее, чем мой O (n)?)

https://leetcode.com/problems/remove-duplicates-from-sorted-array/discuss/477370/python-3%3A-straight-forward-6-lines-solution-90-faster-100-less-memory

Мой оптимизированный код (быстрее, чем 89%)

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        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

Answer 1

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

Это также зависит от того, как усредняется время выполнения в нескольких тестовых случаях; если большинство тестовых случаев предназначено для небольших входов, где решение quadrati c быстрее, то решение quadrati c может выйти вперед в целом, даже если его временная сложность выше. @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')

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

Answer 2

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

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

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

Просто посмотрите на вашу переменную count, в каждой итерации ее значение равно left+1, вы можете вернуть left+1, просто удалив, что уменьшит n на 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), если вы посмотрите на l oop, но, поскольку мы работаем с дублирующими членами, когда я зацикливаюсь на сокращенных членах, в то время как ваш код циклично распространяется на всех членах. Таким образом, время, необходимое для создания этого уникального набора / дикта, будет меньше, чем требуется для вас l oop над этими дополнительными членами и для проверки наличия условий, тогда мое решение может быть быстрее.