Какова временная сложность получения последнего индекса для массива?
array = ["A", "B", "C", "D"]
для данного массива требуется O(1), чтобы указать на первый индекс, равный 0. Поэтому, если я наберу array[0], потребуется O(1), чтобы указать на "A". Но если я напишу array[-1], который указывает на последний индекс 3. Будет ли он перебирать весь массив, чтобы получить последний индекс, или он знает, что массив заканчивается на индексе 3 по умолчанию?
Другими словами, как массив [-1] реализован в python?
Чтение это
Ответы 2
Нативные списки Python представляют собой массивы указателей, и доступ к любому элементу осуществляется за O(1).
Обратите внимание, что это деталь реализации, относящаяся к стандартной реализации Python, известной как CPython. Реализации других языков могут реализовывать списки иначе.
Спасибо за ваш ответ. Я согласен. Доступ к любому элементу занимает O (1). Но когда я хочу получить доступ к последнему элементу, как он напрямую переходит к последнему элементу? Разве указатель не должен перебирать весь массив, чтобы узнать, что это последний элемент?
Список знает свою длину, поэтому доступ к элементам по отрицательному индексу тривиален.
Доступ к любому элементу массива осуществляется в постоянное время, поскольку он известен по ячейке памяти (т.е. по указателю).
Массиву не нужно проходить через предыдущие элементы, чтобы получить доступ к n-му элементу (т.е. он не похож на связанный список). Расположение всех элементов известно заранее, и к ним можно просто получить доступ напрямую.
Обновлено благодаря комментариям.
array[-x] является синтаксическим сахаром для array[len(lst) - x]. Так что это по-прежнему простой постоянный доступ к указателю и не требует времени.
lst[-x] является синтаксическим сахаром для lst[len(lst) - x].
Спасибо. Это очень помогло. Я также не знал, что len() занимает O(1)
@ananya: Если вы знаете C++, вы можете думать о list Python как об эквиваленте std::vector или для Java как о ArrayList. Это просто имя Python для массива с динамическим размером. Несмотря на название, это не связанный список.
Это не массив, это список.