в другой массив по одному, то это считается как задействование доп. памяти O(n) или нет?
foo = [1, 2, 3, 4, 5]
bar = []
*** (N=5 перекладываний)
foo = []
bar = [1, 2, 3, 4, 5]
да О(n)
Что уж прямо непредсказуемым? In [148]: l1 = [i for i in range(1_000_000)] In [149]: sys.getsizeof(l1) Out[149]: 8448728 In [150]: for _ in range(500_000): l1.pop() In [151]: sys.getsizeof(l1) Out[151]: 4752472 То что при реаллокации он потенциально может временную копию сделать, не значит, что мы эту память используем.
Порядок изменился на обратный. Такой хак нужно 2 раза сделать и тогда можно перекладывать списки и без дополнительной памяти
Ну в О нотации мы не смотрим как реализован массив в конкретном языке
Порчдок чего? О чём ты вообще?
Ещё как смотрим.
То есть если один и тот самый алгоритм описать на C++ и питоне, то О нотация по памяти может быть разная?
Сложность разная в зависимости от того, что под капотом у используемой структуры данных.
Мы смотрим на то, какая структура данных используется. Списки в питоне реализоваты на динамических массивах
Если мы будем использовать не динамические массив vector, а встроенные массивы, то "да"
Порядок элементов, которые ты pop-ом достаёшь. Образец с кодом в исходном сообщении предполагал не такое
Обсуждают сегодня