Big-O списка разрезов

Скажем, у меня есть список Python, my_list, который содержит N элементов. Отдельные элементы могут быть проиндексированы с помощью my_list[i_1], где i_1 - индекс искомого элемента. Однако списки Python также могут быть проиндексированы my_list[i_1:i_2], где требуется "срез" списка от i_1 до i_2. Что такое запись Big-O (наихудший вариант), чтобы нарезать список размером N?

Лично, если бы я кодировал "slicer", я бы перебирал от i_1 до i_2, генерировал новый список и возвращал его, подразумевая O (N), это как Python делает это?

Спасибо,

Ответ 1

Получение среза - O (i_2 - i_1). Это связано с тем, что внутреннее представление списка Python представляет собой массив, поэтому вы можете начинать с i_1 и итерации до i_2.

Для получения дополнительной информации см. запись в вики Python

Вы также можете посмотреть реализацию в источник CPython, если хотите.

Ответ 2

согласно http://wiki.python.org/moin/TimeComplexity

это O (k), где k - размер среза

Ответ 3

Для списка размера N и среза размера M итерация на самом деле является только O (M), а не O (N). Так как M часто < N, это имеет большое значение.

На самом деле, если вы думаете о своем объяснении, вы можете понять, почему. Вы выполняете только итерацию от i_1 до i_2, а не от 0 до i_1, а затем от I_1 до i_2.