Size: a a a

Хирьянов Т.Ф., Практика программирования на Python 3 (2019)

2020 May 10

m

mr.slavik in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
вообще сложность pop - O(1)
источник

m

mr.slavik in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
не понимаю где он память потребляет)
источник

AA

AА AА in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
Сложность по чему? Поп же сдвиг делает еще, не просто выкидывает элемент
источник

m

mr.slavik in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
странно было бы реализовать списки добавление и удаление элементов из которых имеет не константную сложность ассимптотическую
источник

КК

Кирилл Картвелишвили... in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
mr.slavik
вообще сложность pop - O(1)
O(n) должно быть
источник

AA

AА AА in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
Так что о(н) по идее
источник

AA

AА AА in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
Сдвинуть весь массив надо поэлементно
источник

КК

Кирилл Картвелишвили... in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
mr.slavik
странно было бы реализовать списки добавление и удаление элементов из которых имеет не константную сложность ассимптотическую
в связных списках добавление и удаление за O(1), но не в питонячих
источник

m

mr.slavik in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
AА AА
Так что о(н) по идее
нет
источник

AA

AА AА in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
Кстати, хирьянов об этом и граорил в лекциях, что аппенд в конец дешевый, но в начало дорогой
источник

m

mr.slavik in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
удаление элемента из списка константную сложность имеет
источник

m

mr.slavik in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
AА AА
Сдвинуть весь массив надо поэлементно
зачем, если это список
источник

AA

AА AА in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
mr.slavik
удаление элемента из списка константную сложность имеет
Поп - удаление со сдвигом
источник

AA

AА AА in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
источник

AA

AА AА in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
mr.slavik
зачем, если это список
Еу это не совсем же список в питоне) там по индексу обращение, а не указателю
источник

КК

Кирилл Картвелишвили... in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
ну здесь рассказано, что есть некий запас, то есть когда мы создаём в питоне пустой список, это значит, что для него уже выделена некая память, и несколько первых добавлений, удалений, чтобы то ни было будут за O(1) происходить. но рано или поздно дойдём до момента, когда память рядом вокруг списка занята чем-то другим. и тогда надо будет создавать новый массив
источник

AA

AА AА in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
Если бы это список был - то там был бы поиск за о(н), кстати, так что все равно не о(1)
источник

КК

Кирилл Картвелишвили... in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
а может в питоне не делается сдвиг. удаляется первый элемент, а указателю на первый элемент присваевается ссылка на следующий. всё равно под капотом сишная арифметика указателей.
источник

AA

AА AА in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
Странно, в статье на хабре одно, а в лекциях другое вроде было)
источник

AA

AА AА in Хирьянов Т.Ф., Практика программирования на Python 3 (2019)
Причем remove O(n) , a pop O(1)
источник