Спасибо!
Ivan Zelenkov
28 уровень
Почему Big O Stack реализованный как LinkedList (top last) при pop операции будет O(N), а при push O(1)
Решен
Комментарии (14)
- популярные
- новые
- старые
Для того, чтобы оставить комментарий Вы должны авторизоваться
Flexo Bending Unit #3370318
2 мая 2021, 19:15
Ммм, а смысл от такой реализации?
вот православный стек:
и у него что pop(), что push() O(1) 0
Ivan Zelenkov
2 мая 2021, 19:44
Смысл понять эту реализацию, а то что на счет использования уже другое дело
0
Flexo Bending Unit #3370318
2 мая 2021, 19:53
если честно, я не понимаю, почему в top last должен быть O(n). LinkedList - это двусвязный же список, у него во внутренних полях хранятся ссылки что на первый, что на последний элемент. если мы будем добавлять (push() ) элемент в конец, мы просто должны взять ссылку bottom и указать bottom.prev = newNode, newNode.next = bottom, bottom = newNode, это понятно что o(1), но обратная же операция pop() не сложнее. 🤷♂️
0
Justinian Judge в Mega City One Master
2 мая 2021, 22:18
а почему именно двусвязный? вариантов много, стек обычно на односвязном реализуют, хотя опять же, кто как хочет, так и пишет
0
Flexo Bending Unit #3370318
2 мая 2021, 23:35
ну я про тот, в утиле находится. подумал, что готовые популярные реализации списков рассматриваются
0
Justinian Judge в Mega City One Master
2 мая 2021, 23:53
та я понимаю, но если анализировать картинку, где автор картинки допускает для связного списка O(N) доступ к первому/последнему элементу, такое при односвязном разве что возможно ну и возможно при некоторых других, отличных от двусвязного списка, вариациях.
Согласен с тобой, Ксенией, тут нам остается только гадать и пытаться уловить контекст
0
Ksenia Volkova Java Developer в DXC Master
2 мая 2021, 19:06
top last - это в смысле LIFO?
0
Ivan Zelenkov
2 мая 2021, 19:35
Не, это имеется в виду, что верхом является последний элемент. Препод, показал что мы имеем Stack + LinkedList и top last это данный верх. Очень запутанно для меня это
0
Ksenia Volkova Java Developer в DXC Master
2 мая 2021, 20:34
Мне кажется, оно запутано твоим преподавателем. Первый раз вижу такую терминологию...
Что должны делать методы pop и push в этом случае?
В стандартной ситуации push добавляет элемент в начало, pop удаляет и возвращает элемент из начала. И большое O у них будет одинаковым.
0
Ivan Zelenkov
2 мая 2021, 22:56
Согласен, запутал
0
Justinian Judge в Mega City One Master
2 мая 2021, 23:12
да, попытался представить чтобы для стека, как LIFO структуры, pop и push отличались, не получилось.
В принципе, табличка на картинке понятна,если принять за основу, что под линкедлист имеется ввиду односвязный список, и поправить случай, описанный ТС на O(N)/O(N)
тогда вроде все логично и становится на свои места, даже с учетом неортодоксальной терминологии, хоть вроде и понятной, верх стека находится на первом элементе или на последнем.
Вопрос зачем стек реализовывать так, чтобы была сложность O(N) оставим на откуп преподу.
+2
Flexo Bending Unit #3370318
2 мая 2021, 23:38
вот-вот, что-то напутано, и это надо уточнить у преподавателя обязательно. не исключено, что автор получит дополнительные очки в глазах преподавателя, потому что захотел разобраться и нашёл ошибку)
+2
Justinian Judge в Mega City One Master
2 мая 2021, 23:54
согласен, хороший вопрос на уточнение и заработать можно баллы.
0
Ivan Zelenkov
3 мая 2021, 01:42
Да, согласен. Спасибо всем!
0