В рейтинге участвует:

групп:

каналов:

Виртуальный сервер на SSD - недорого!

Аренда выделенных и виртуальных серверов (VDS/VPS), хостинг, аренда IP-адресов, администрирование, круглосуточная поддержка

qwarta.ru подробнее

Резервное копирование с проверкой на вирусы!!!

Удобный сервис создания резервных копий на любой сервер сети интернет. Отслеживайте изменения, проверяйте на вирусы. Надежно защитите свой бизнес!

go.backupland.com

Выбираете сервер? Любая конфигурация на заказ!

Аренда физических серверов любых конфигураций под любые запросы - 1С бухгалтерия, игровые сервера, нагруженные проекты, интернет-магазины!

qwarta.ru подробнее

Size: a a a

learn.java

3748 membersпожаловаться на группу
2020 September 12

I

Igor in learn.java
Эд
Кажется, тут ошибка в худшем времени для LinkedList. Верно? Я про вставку (O(n) должно быть, ведь итерируем по элементам, пока не найдём, куда вставить)
Видимо, тут имеется в виду add(Object o), который добавляет в конец
источник
20:34пожаловаться#1

АК

Андрей Карчевский... in learn.java
Андрей Карчевский
Хорошая книжка?
источник
20:34пожаловаться#2

I

Igor in learn.java
Андрей Карчевский
Хорошая книжка?
Тут чат по джаве, а не по андроиду. Лучше в @android_ru спросить
источник
20:35пожаловаться#3

АК

Андрей Карчевский... in learn.java
Igor
Тут чат по джаве, а не по андроиду. Лучше в @android_ru спросить
Извиняюсь, спасибо
источник
20:35пожаловаться#4

Э

Эд in learn.java
Эд
Кажется, тут ошибка в худшем времени для LinkedList. Верно? Я про вставку (O(n) должно быть, ведь итерируем по элементам, пока не найдём, куда вставить)
Я подумал. Мне кажется, автор имел ввиду время вставки уже после поиска
источник
20:36пожаловаться#5

em

ek man in learn.java
JVM преобразовывает весь байт-код сразу в машинный или ЖВМ часть компилирует, а часть интерпретирует?
источник
20:46пожаловаться#6

Д

Дима in learn.java
sticker.webp
(13.03 Кб)
источник
20:49пожаловаться#7

A

Anton in learn.java
Эд
Кажется, тут ошибка в худшем времени для LinkedList. Верно? Я про вставку (O(n) должно быть, ведь итерируем по элементам, пока не найдём, куда вставить)
Это для однонаправленного списка, поэтому вставка в конец O(n).
Для двунаправленного java.util.LinkedList вставка/удаление в конец O(1), в середину не более O(n/2), т.к. в середину он идёт ближайшим путём от конца или начала.
https://medium.com/@mckenziefiege/arrays-linked-lists-and-big-o-notation-486727b6259b
источник
21:10пожаловаться#8

ПФ

Паша Финкельштейн... in learn.java
Anton
Это для однонаправленного списка, поэтому вставка в конец O(n).
Для двунаправленного java.util.LinkedList вставка/удаление в конец O(1), в середину не более O(n/2), т.к. в середину он идёт ближайшим путём от конца или начала.
https://medium.com/@mckenziefiege/arrays-linked-lists-and-big-o-notation-486727b6259b
Вообще никто не говорит что у однонаправленного списка у нас нет ссылки на последний элемент 😉
источник
21:20пожаловаться#9

A

Anton in learn.java
Паша Финкельштейн
Вообще никто не говорит что у однонаправленного списка у нас нет ссылки на последний элемент 😉
Теория такая непрактичная)
источник
21:21пожаловаться#10

ПФ

Паша Финкельштейн... in learn.java
Обычно теория говорит о направлениях ссылок. А о ссылках на конец там обычно не написано. Но нам и правда могут не давать ссылку до первого добавления в конец, а там уже мы можем её себе сами прихранить ) Но есть нюанс, как обычно
источник
21:23пожаловаться#11

A

Anton in learn.java
Паша Финкельштейн
Обычно теория говорит о направлениях ссылок. А о ссылках на конец там обычно не написано. Но нам и правда могут не давать ссылку до первого добавления в конец, а там уже мы можем её себе сами прихранить ) Но есть нюанс, как обычно
Так можно и многократную вставку в середину в цикле довести примерно O(1), если  вынести операцию поиска отдельно, вернув какой-нибудь неизменяемый снаружи Node. А потом только принимать его в операцию вставки.
источник
21:33пожаловаться#12

DS

Dmitriy Shilnikov in learn.java
Anton
Это для однонаправленного списка, поэтому вставка в конец O(n).
Для двунаправленного java.util.LinkedList вставка/удаление в конец O(1), в середину не более O(n/2), т.к. в середину он идёт ближайшим путём от конца или начала.
https://medium.com/@mckenziefiege/arrays-linked-lists-and-big-o-notation-486727b6259b
O(n/2) разве вообще правильная запись? Чем это отличается просто от O(n)?
источник
21:39пожаловаться#13

VS

Vlad S in learn.java
Dmitriy Shilnikov
O(n/2) разве вообще правильная запись? Чем это отличается просто от O(n)?
Ничем. Иногда пишут О(n/k), смысл как и у О(n)
источник
21:41пожаловаться#14

A

Anton in learn.java
Dmitriy Shilnikov
O(n/2) разве вообще правильная запись? Чем это отличается просто от O(n)?
Я имел ввиду сравнительно. Если n - общее количество элементов в листе, то в односвязном списке (без прямой ссылки на последний элемент) худший случай будет O(n), а в двухсвязном худший случай O(n/2), наклон линии с ростом элементов будет пониже. В более общем смысле запись O (n/2) конечно не имеет большого смысла.
источник
21:57пожаловаться#15

ПФ

Паша Финкельштейн... in learn.java
Dmitriy Shilnikov
O(n/2) разве вообще правильная запись? Чем это отличается просто от O(n)?
неправильная. При константном коэфициенте запись не меняет. n/k — корректно кога у нас ещё есть какая-то переменная k (например если бы линкедлист был поделен на заранее неизвестное количество сегментов k)
источник
22:02пожаловаться#16

A

Anton in learn.java
Паша Финкельштейн
неправильная. При константном коэфициенте запись не меняет. n/k — корректно кога у нас ещё есть какая-то переменная k (например если бы линкедлист был поделен на заранее неизвестное количество сегментов k)
Когда 2 алгоритма, где а одном константно k=1, в другом константно k=2 -  оба O(n), да, поэтому одинаковы, фиг с ним, что один в два раза быстрее)
источник
22:08пожаловаться#17

ПФ

Паша Финкельштейн... in learn.java
Anton
Когда 2 алгоритма, где а одном константно k=1, в другом константно k=2 -  оба O(n), да, поэтому одинаковы, фиг с ним, что один в два раза быстрее)
всё так, O-нотация ничего не говорит о реальной сложности, она только что-то говорит об алгоритмической
источник
22:09пожаловаться#18

DS

Dmitriy Shilnikov in learn.java
Вообще гугл склоняется к тому, что O(n/2) писать всё-таки можно
источник
22:10пожаловаться#19

DS

Dmitriy Shilnikov in learn.java
Но это абсолютно то же самое, что O(n)
источник
22:10пожаловаться#20