Сложность O(n).
Если делать замеры для списков разных размеров, то увидим что время выполнения растёт линейно, что подтверждает сложность O(n).
Если же сложность не O(1), то почему? Ведь перемещать ничего не надо.
Удаление среза реализовано как проход по удаляемым элементам с вызовом Py_DECREF на каждый.
З.Ы. чисто теоретически сложность O(1) может быть для крайнего случая с pos = 0, если целиком уничтожается вся структура (но так ли это в реальности надо проверять) и pos = n - 1.
Ну и надо разделять абстрактную алгоритмику и конкретные бенчмарки.
Код.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()