Какова временная сложность del[pos:] для списка в Python?

Question

[d_ilyich]

Если удалить правую часть списка с помощью

del my_list[pos:]

то по времени это будет O(1) или O(N) ? Как это можно проверить? Я попытался оценить разницу с помощью pytest-benchmark на таком коде:

def del_slice() -> None:
    for _ in range(10_000):
        my_list = [1]*1_000_000
        del my_list[500_000:]

def del_last() -> None:
    for _ in range(10_000):
        my_list = [1]*1_000_000
        for _ in range(500_000):
            del my_list[-1]

def test_del_slice(benchmark):
    benchmark(del_slice)

def test_del_last(benchmark):
    benchmark(del_last)

Результаты:

----------------------------------------------------------------------------
Name (time in s)          Min                 Max                Mean       
----------------------------------------------------------------------------
test_del_slice        43.8683 (1.0)       57.6685 (1.0)       48.2936 (1.0) 
test_del_last        203.9794 (4.65)     239.6570 (4.16)     226.9720 (4.70)
----------------------------------------------------------------------------

Потом поменял немного:

def del_slice2() -> None:
    my_list = [[1]*500_000 for _ in range(5_000)]
    for l in my_list:
        del l[250_000:]

def del_last2() -> None:
    my_list = [[1]*500_000 for _ in range(5_000)]
    for l in my_list:
        for _ in range(250_000):
            del l[-1]

Результаты:

-------------------------------------------------------------------------
Name (time in s)         Min                Max               Mean       
-------------------------------------------------------------------------
test_del_slice       27.8310 (1.0)      36.0834 (1.0)      30.5021 (1.0) 
test_del_last        87.6777 (3.15)     97.6951 (2.71)     93.4931 (3.07)
-------------------------------------------------------------------------

По моим представлениям, если бы del_slice выполнялся за O(1), разница была бы больше. Возможно, я неправильно замеряю. Если же сложность не O(1), то почему? Ведь перемещать ничего не надо.

Answer 1

[dim5x]

Сложность O(n).
Если делать замеры для списков разных размеров, то увидим что время выполнения растёт линейно, что подтверждает сложность O(n).

З.Ы. чисто теоретически сложность O(1) может быть для крайнего случая с pos=0, когда целиком уничтожается вся структура, но так ли это в реальности надо проверять.
Ну и надо разделять абстрактную алгоритмику и конкретные бенчмарки.

Код.

import time
import matplotlib.pyplot as plt


def test_del_slice_complexity():
    sizes = [10 ** 3, 10 ** 4, 10 ** 5, 10 ** 6]
    times = []

    for n in sizes:
        # Создаем список
        my_list = [1] * n

        # Замеряем время удаления
        start_time = time.perf_counter()
        del my_list[n // 2:]  # Удаляем 50% элементов
        end_time = time.perf_counter()

        elapsed = end_time - start_time
        times.append(elapsed)

        print(f"n = {n:>7}: {elapsed:.6f} сек")

    # Визуализация результатов
    plt.figure(figsize=(10, 5))
    plt.plot(sizes, times, 'o-', label='Измеренное время')
    plt.plot(sizes, [times[0] * n / sizes[0] for n in sizes], '--', label='Ожидаемое линейное время')
    plt.xscale('log')
    plt.yscale('log')
    plt.xlabel('Размер списка (n)')
    plt.ylabel('Время выполнения (сек)')
    plt.title('Сложность операции del my_list[n//2:]')
    plt.legend()
    plt.grid(True)
    plt.show()


if __name__ == "__main__":
    test_del_slice_complexity()

Comments

[fenrir]

Я не у компа чтобы посмотреть внимательно исходники, но готов поставить сотку, что описанный случай это корнеркейс при котором просто ob_size обрезается за O(1).

А линейно растёт время создания списка, которое тоже попало в измеряемую функцию.

[dim5x]

fenrir,
Создание списка выше, измеряю только del.

start_time = time.perf_counter()
del my_list[n // 2:]  # Удаляем 50% элементов
end_time = time.perf_counter()