Константа же
Да, верно, а на это
> А какая сложность у смены указателя элемента, который предшествует удаленному?
забей, там копейки.
>>254027242 (OP)
> пробежаться до 1024 элемента - это сложность O(n)
Вот тут ты ошибся в рассуждениях, пробежаться до 1024-го элемента всегда займет одно и то же время, независимо от длины списка
Пиздец, я еще больше запутался. Почему? У нас же список, ссылки на элемент нет, есть только информация о том, что нужно ебнуть 1024 - ый элемент. Адрес то 1024-го мы не знаем.
Ты в шары ебешься? Прочитай что на следующей странице. Операции с рандомным элементом для связаного списка это O(n) Операции с головой O(n)
* С головой - O(1)
Ну так и будет ответ O(n), как и написано в ОП посте, а не O(1) - как написал ты - >>254027834
Чтобы дойти до 1024-го элемента, тебе надо 1024 шага.
И похуй сколько там элементов после него.
То есть от количества элементов время прохождения до 1024-го никак не изменится.
> как написал ты
Это писал не я
Или троль или даун.
Пик 2 в качестве доказательства того, что они дебилы. Или я не прав?
Бамп
Бамп
Надеюсь ты за это говно хотя бы не платил лол?
В задании 16 они имели в виду массив, бай зе вей это не меняет ответ.
O(1), то есть константа. У тебя сложность этого алгоритма (удаление 1024-го элемента) будет одинакова при любой длине списка.
Алгоритм будет такой тебе нужно найти 1023 элемент, записать в него ссылку на 1025 и всё, вне зависимости от n.
Если бы в задании нужно было удалить произвольный элемент, то O(n).
А если список длиной 100?
Есть структурка такая, ArrayList. В ней как раз время доступа константное, это массив который расширяется при необходимости.
На пикриле список односвязный, поэтому нужно сначала найти предыдущий элемент, пройдя n-1 элементов, потом узнать указатель на n+1 элемент, и записать его в n-1й. Собственно, поэтому сложность O(n).
Ебать ты тупой
В задании спрашивается про 1024 элемент, а не случайный
>>254030099
Нет, ты. У тебя исходно нет указателя на 1023 элемент, его надо найти. Асимптотическая сложность доступа по индексу в односвязном списке O(n).
Сука, кто так задачу формулирует, по башке камнем бить надо. Поэтому пидарашня везде и сосет. Открываешь любой западный задачник, там все понятно изложено со схемами, ясно и на пальцах, тут же 10 интерпретаций можно из такой постановки вывести. Даже схему блядь нормально нарисовать не могут, все какими-то намеками ебнутыми.
Раз просят найти 1024-й, значит как минимум 1024
Сколько операций ты сделаешь, если длина списка 1500? Сколько операций, если 100000?
Сколько операций ты сделаешь, если длина списка 1500? Сколько операций, если 100000?
Знаешь как найти 1024 элемент? Начиная с head идти по указателю на следующий 1024 раза? Теперь смотри.
Сколько операций будет совершено при длине 1024? 1024
При длине 10000? 1024
При длине 1000000? 1024
Какой вывод можно сделать? Правильно, сложность не зависит от длины списка, то есть она постоянная, иначе говоря константная. А константная сложность это O(n)? Правильно, нет, она O(1)
Это какая-то ВУЗовская дичь?
мимовкатун
Так это задача, в которой первый ответ, приходящий на ум большинству (мне в том числе) неверный, т к думать лень, а не формулировка плохая
Окей, сложность О(1024). Но тк на константу всем похуй, то О(1)
> А какая сложность у смены указателя элемента, который предшествует удаленному?
Долбоеб, удаление это и есть перезапись указателя предыдущего элемента на указатель элемента который следует через удаляемый.
Поддерживаю этого анона. Вдобавок в таких простых задачах можно явно написать формулу количества операций от n. Если подобные простые рассуждения не помогают разобраться, выпиши формулу и найди O(n).
Список может быть как с массивом под капотом, так и как связная структура.
Если массив, то доступ по индексу и сдвиг.
Если связная структура, то поиск и константная смена указателей.
В любом случае O(n)
Тебе выше уже несколько раз объяснили почему O(1).
O(n) если бы например просили удалить элемент по середине.
O(1024) -> O(1)
O(n/2) -> O(n)
Ох лол. Тебе про асимптотическую сложность, а ты про частный случай.
Давай по-другому. У тебя есть массив из 100 элементов. Сложность сортировки квиксортом в среднем O(n*log(n)). Какова сложность его сортировки? Константная, скажешь, т.к. количество элементов всегда одно и то же?
Как ты рассуждаешь, когда приходишь к O(n)?
Ебан, перечитай условие задачи. Там требуется найти 1024й элемент.
У тебя АЛГОРИТМ НАХОЖДЕНИЯ 1024 ЭЛЕМЕНТА будет
>1024
1024 это не n
В таких задачах нужна сложность не частного случая, а общая.
Условие задачи перечитай
Какой же ты упрямый! Сдаюсь, ты подебил.
Ответы перечитай. По твоей логике там нет правильного ответа. Ибо ответ O(1) так как удаление константное не подходит.
А O(N) подходит, так как упоминается поиск, который у тебя есть.
Ну и N и n немного разные буквы.
По-моему ты просто видел, что какие-то алгоритмы имеют известные оценки и не понимаешь, что они вообще значат
В задаче не требуется поиск
То что задачу долбаёб формулировал это другая история.
Я привёл пример выше когда твой вариант будет верным - если бы просили удалить элемент по середине, например
Вопрос поставлен ебануто как ТЗ ирл и вертится как дышло, тут либо обсуждать с человеком который его задал, либо слать нахуй такие галеры.
Хорошо что я в свое время такое говно не проходил.
300к/нс синьор
Давай, рассказывай мне про понимание, гражданин константа. У тебя проход по списку из долгого обхода превратился в моментальный доступ, пиздец, ещё и других поучаешь.
Окей, требуется удалить первый элемент. Какая сложность будет?
>>254031138
Доступ не моментальный, он требует одинаковое количество операций независимо от длины списка.
Окей, требуется удалить 1кк элемент. Какая сложность будет?
Да. Так же как многие задачи на строки требуют работы с мапой символ (lower case english only) - число (индекс, кол-во повторений и т.д.) и работа с этим списком считается за константу. Потому что твоя обоссаная сотня – ничто в сравнении с N.
Не поверишь - O(1)
Раз ты синьор-помидор, значит, логично, что когда то был джуном. И как же тебя угораздило вкатиться на джуна без знания всего этого говна? Это ведь на каждом собесе спрашивают
> И как же тебя угораздило вкатиться на джуна без знания всего этого говна?
Чел, 10-15 лет назад достаточно было показать, что ты в состоянии поднять LAMP и написать простенькое говно на пыхе. А не вертеть жопой с конкурсом 1кк человек на место.
Ох, опять эти мантры про не такое ТЗ. Щас заказчик для тебя всё разжуёт, ещё и алгоритм распишет. На синьорском уровне пора бы уже уметь читать между строк, угадывать и предлагать бизнесу лучшие решения самостоятельно. А не писать по каждому чиху заказчику и потом оправдываться при проёбе сроков тем, что ты не знал деталей имплементации бизнес-логики
Когда ты знаешь, где находится элемент, его место в списке, например 1024, то поиск выполнять не нужно. Для доступа к элементу нужно будет пройти по списку, но всегда ты это сделаешь за одинаковое количество операций, каким бы длинным не был список.
Подумай спокойно, тебе ведь не говорят, что ты глупый или что-то в этом духе, пытаются объяснить и помочь разобраться. Че ты, мистер константа, обидно же
Ну наверно я общался с людьми просто, а не с бездушными машинами тестами написанными анальниками с дислексией и неспособностью посмотреть на свой же текст под другими углами.
Чел, ну ты абсолютно не понимаешь сути. Ты как макака которая вычитала баззворды и запомнила их. Тебе уже разные примеры привели в этом треде, и так и сяк, а ты пиздец упираешься как баран. Я не буду повторно объяснять почему ты не прав, просто иди нахуй
Нас тут как минимум 2. И это не троллинг
А я не говорю что ТЗ должно быть идеально расписано.
Просто тут нужна обратная связь. Спросить, от нас хотят узнать знаем ли мы стоимость удаления элемента в связном списке (например при итерации) когда мы уже на нём.
Или хотят проверить, знаем ли мы, что для удаления в связном списке нужно добежать до элемента.
>>254031488
Зависит ли скорость работы функции доступа к 1кк-тому всегда к нему, не к вашему обоссаному случайному, а имеено к этому индексу, мы его захардколили нахуй элементу связного списка от его размера? Теперь соедините это с тем, что показывает О.
Там же в таблице как раз O(1)
Я на удаление посмотрел, но сути это не меняет
А вы прочли вообще, что написано курсивом в задании? Доступа по индексу НЕТ, константного времени НЕТ, оно линейное - O(n). Удаление - константное, да, O(1)
Да, я другой мистер константа
Пиздец ты даун, тебя уже весь сосач хуесосит.
Доступ к произвольному элементу O(n), а у тебя известен номер, он никак от n не зависит.
А вот удаление например n//2-того элемента, внезапно, будет происходить за O(n).
Как скажешь, мистер константа. Я тоже объяснял.
>>254031582
И тебе я тоже объяснял. Меня не слушаешь, других послушай.
https://stackoverflow.com/questions/1895769/time-complexity-of-node-deletion-in-singly-and-doubly-linked-lists
> in a singly-linked list, the pointer to the previous node is unknown and can be found only by traversing the list from head until it reaches the node that has a next node pointer to the node that is to be deleted. The time complexity in this case is O(n)
Или вот ещё https://stackoverflow.com/questions/14048143/why-is-deleting-in-a-single-linked-list-o1
Никто не говорит про доступ по индексу.
У тебя при различной длине массива, алгоритм будет совершать одинаковое число операций - 1024.
O(N) - линейная сложность, то есть у тебя количество операций должно линейно зависеть от N.
Ты можешь нарисовать график сложности доступа к захардкоженному 1кк-тому элементу для списка размером от 1кк до 2кк? и увидеть что это обоссаная прямая
Ничто не мешает написать
head.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next.next
Так что я тоже записываюсь в секту свидетелей константы.
Обоссаная прямая - это и есть O(n), линейная сложность. Что ты мне этим доказать хотел я так и не понял. Пусть количество операций чтения одинаковое для 1024 элементов. 1024 - это и есть n. Чтобы удалить n элемент нужно совершить n операций чтения из листа. Почему, я объяснял в этом >>254029911 посте. А в этом >>254031813 тебе объяснили другие анонимы со stackoverflow.
Пиздец, столько гонору у вас, ребятки. RTFM.
Доступ по индексу это линейный в общем случае, для произвольного индекса, так как от его значения зависит сколько элементов ты пробежишь. В задаче спрашивается сложность удаления не элемента с индексом i например, а элемента с индексом 1024.
Именно что N-й, а не 1024. Когда говоришь об N-м речь идёт о количестве операций в худшем случае, а когда о 1024-м - о конкретном случае, а не о многообразии потенциально возможных
Ну список и список, главное что элементы не связаны и доступ по индексу. В разных языках это может по-разному называться.
Из чего следует, что доступ к 1кк+1 элементу будет происходить за то же время, что и к 1кк? Не понял график.
>>254032286
В этом конкретном случае 1024 и есть n.
И вообще сказано достаточно, sapienti sat.
Доступ к тому же элементу (с тем же индексом), но в списке размером больше будет тем же.
График для дошколят не понял, зато латынью выебываться горазд. Да
Я хз что за линейная часть. Пояснения графика беру назад
Окей, это так. Я не понимаю почему свидетели константы считают, что если количество операций чтения одно и то же для i-го элемента, обход листа из O(n) превращается в O(1). Ну в упор не понимаю с чего вдруг взялось это упрощение, и уже начинаю сомневаться в своей способности рассуждать логически.
Доступ к первому элементу, n=1, окей, время доступа O(n). Доступ к 1кк элементу, n=1kk, время доступа O(n). Где я ошибаюсь?
>>254032465
А ты пожуй говна.
Давай разделим все эти индексы немного.
n - количество элементов списка.
Сложность удаления i-го элемента по-хорошему O(i).
Сколько операций нужно для удаления i-го элемента?
i = O(i).
Если тебе всегда нужно удалять элемент с одним и тем же номером, то и операций всегда будет одинаковое количество. В задаче с первого пика это 1024 = O(1)
У тебя n не может быть привязано к константе.
> Доступ к первому элементу, n=1, окей, время доступа O(n)
то есть ты не можешь сказать, n=1 значит время O(n). n в функции O - это длина массива, если так понятнее будет.
>>254032858
Окей, убедили. Спасибо за разъяснения.
>>254032814
Тут я не прав, никаких O от i, от n конечно. Нагромоздил глупости
Потому что n в Big O notation стремится к бесконечности. Если бы ты получал два аргумента - список и номер элемента, то да, комплексити было бы O(n). Но ты получаешь только список (размер которого стремится к бесконечности для оценки комплексити), а номер элемента у тебя константа, и никак не может быть n. Все твои фантазии и "доказательства" со списком короче 1024 элементов полная хуета, ты не понимаешь определения нотации в которой пытаешься выразить сложность.
Полная хуета у тебя в штанах, быдлан.
>пук
Какие результаты теста, ОП? Победил?
>Операции с рандомным элементом для связаного списка это O(n)
Ты еблан? В задаче ни слова нет про РАНДОМНЫЙ элемент.
Там речь идет про конкретный элемент.
Для любого n сложность будет одна и та же.
Тред не читал. Сложность смены указателя либо О(1) если ты его запомнил либо О(1023) если опять до него надо пиздюхать, то есть О(2n) что вообщем тоже O(n)
Лол, ты не знаешь разницу между списком и массивом?
Или не знаешь, что списки бывают не только связанными?
Тебе написали русским языком, что список индексированный, но до тебя это так и не дошло.
>1024 - это и есть n.
Блядь, вот из-за таких долбоебов современный софт и является полным говном.
Я в проге особо не шарю, но вроде как O(1), потому что все что нужно это перевести указатель из 1023 на 1025 вместо 1024, для этого достаточно узнать, какой адрес у 1025 элемента, те дойти до него. Это делается за 1025 шагов вне зависимости от размера списка
Срач буквально из-за ничего, просто пара макак-вкатунов в треде не проходили даже одного семестра вузовской математики где учат пределы.
Оп-студент, давай про0оди курс и ищи стажку. Удачи
Сложность определяется при n->inf
>математики где учат пределы
Лол, еблан не осилил даже родной язык.
Еблан, также, думает, что здесь какие-то сраные пределы играют какую-то сраную роль.
Еблан, также, думает, что его сраное мнение кого-то взволнует.
Але, еблан, таких, как ты, тут и так как говна за баней.
O(n)
Тебя ввело в заблуждение, указание конкретного элемента. Хоть первый, хоть 99999 удаляй, асимптотика от этого не изменится
>Пределы не играют никакой роли
>В треде про оценку сложности
Хоть бы потоньше пробовал
Блядь, какой ты тупой.
Попробуй хотя бы прочесть задание. От первой буквы до последней.