m
вообще сложность pop - O(1)
Size: a a a
2020 May 10
m
не понимаю где он память потребляет)
AA
Сложность по чему? Поп же сдвиг делает еще, не просто выкидывает элемент
m
странно было бы реализовать списки добавление и удаление элементов из которых имеет не константную сложность ассимптотическую
КК
вообще сложность pop - O(1)
O(n) должно быть
AA
Так что о(н) по идее
AA
Сдвинуть весь массив надо поэлементно
КК
странно было бы реализовать списки добавление и удаление элементов из которых имеет не константную сложность ассимптотическую
в связных списках добавление и удаление за O(1), но не в питонячих
m
Так что о(н) по идее
нет
AA
Кстати, хирьянов об этом и граорил в лекциях, что аппенд в конец дешевый, но в начало дорогой
m
удаление элемента из списка константную сложность имеет
m
Сдвинуть весь массив надо поэлементно
зачем, если это список
AA
удаление элемента из списка константную сложность имеет
Поп - удаление со сдвигом
AA
зачем, если это список
Еу это не совсем же список в питоне) там по индексу обращение, а не указателю
КК
ну здесь рассказано, что есть некий запас, то есть когда мы создаём в питоне пустой список, это значит, что для него уже выделена некая память, и несколько первых добавлений, удалений, чтобы то ни было будут за O(1) происходить. но рано или поздно дойдём до момента, когда память рядом вокруг списка занята чем-то другим. и тогда надо будет создавать новый массив
AA
Если бы это список был - то там был бы поиск за о(н), кстати, так что все равно не о(1)
КК
а может в питоне не делается сдвиг. удаляется первый элемент, а указателю на первый элемент присваевается ссылка на следующий. всё равно под капотом сишная арифметика указателей.
AA
Странно, в статье на хабре одно, а в лекциях другое вроде было)
AA
Причем remove O(n) , a pop O(1)