Comments 35
O(n), где n — количество элементов в списке, так как указатели проходят по каждому элементу максимум один раз.
Не правда. "Быстрый" указатель может по циклу сделать очень и очень много полных оборотов.
Ну и по статье - разбор баянистых элементарных задачек надо делать не так. Люди, которые их уже знают, от вашей статьи не получили ничего. Люди, которые их не умеют решать, от вашей статьи тоже не получили ничего, потому что им ничего не понятно. Максимум, что они тут могут сделать - это выучить код наизусть. Сомнительной полезности действие.
Вам надо не только приводить код решения (причем два раза: первый раз текстом, второй раз кодом), а объяснять, почему и как оно работает.
скорее всего там никогда не будет O(n*n), а всегда будет O(k*n) где k*n < n*n, что в BigO() нотации эквивалентно O(n). У вас n элементов в списке и кольцо на первый элемент, это даёт 2*n в максимуме.
Там все еще будет O(n), потому что медленный указатель, действительно, пройдет по каждому элементу не более 1 раза (после того, как он ступит на цикл, быстрый догонит его раньше, чем он сделает полный круг). Быстрый делает 2 шага на 1 шаг медленного, поэтому общее количество ходов будет не больше 3n.
Вот только это надо все расписать.
Вот только это надо все расписать.
почему вы так считаете?)
Потому что иначе в статье нет никакой пользы. Вы же зачем-то попытались аргументировать, почему там O(n) будет? Правда, с ошибкой.
Потому что иначе в статье нет никакой пользы
ну видимо нет пользы для вашего уровня, надеюсь найдутся люди, для которых статья будет полезной)
надеюсь найдутся люди, для которых статья будет полезной)
Очень вряд ли. Вот так как вы объясняете - начинающим не понятно. Говорю как человек с опытом преподавания. Ваш текст вообще лишь дублирует код. Он должен объяснять не "что", а "как", "откуда" и "почему". Поскольку задача очень широко известная, то любой не совсем начинающий ее уже знает.
Соответственно, вам надо или задачи посложнее и не такие известные брать, или разъяснять почему вот это работает в тексте.
Если есть примеры, где объясняется лучше, напишите, гляну
Например, тут: https://cp-algorithms.com/others/tortoise_and_hare.html
Спасибо за пример, но мне больше нравится формат в котором я пишу, для новичков, а не с математическими доказательствами)
Ну совсем без математики нельзя. Все-таки алгоритмы - это computer science, которая является областью математики. Ну можно хотя бы словами объяснить почти все.
Основная идея: когда медленный указатель зайдет на цикл, за одну итерацию расстояние между ними уменьшается на 1. В итоге за конечное число шагов (меньше длины цикла) быстрый указатель догонит медленного. Было между ними растояние L (если считать по циклу от быстрого), а стало L+1 - 2 = L-1 (+1 - медленный ушел вперед -2 - быстрый пошел вслед за ним). Поэтому, кастати, не надо проверять, не догнал ли быстрый указатель медленный дополнительно в середине его длинного шага - заяц через черепаху не перепрыгнет. Поэтому алгоритм рано или поздно остановится.
Еще можно было бы объяснять прогрессивно, по уровням, как до этого можно додуматься. Начнем с задачи проверить, является ли список замкнутым циклом, или линией вообще без циклов. Можно проверять одним указателем совпадение с перым элементом. Но если первый элемент не на цикле, то это не работает. Надо взять какой-то элемент в цикле. Но неизвестна же длина начала, поэтому нельзя сначала сделать много шагов, ибо неясно, а сколько их будет достаточно. Значит надо этот помеченный элемент в цикле двигать вперед. Но тогда сам указатель надо двигать на 2 шага, чтобы продвижение вперед, все-таки было.
И про время работы, если бы вы хотя бы примерно стали считать, а сколько там операций то происходит, то не ошиблись бы в рассуждениях.
Например, тут: https://cp-algorithms.com/others/tortoise_and_hare.html
По времени: O(n), где n — количество элементов в списке, так как указатели проходят по каждому элементу максимум один раз.
У вас ошибка, указатель, который быстрый, может пройти по некоторым элементам списка не один раз (видимо от 1 до 2*n раз, в среднем n/2).
А O(n) там будет из-за константного характера числа итераций, то есть будет O(k*n) где k*n < n*n, хотя в комментариях и есть вырожденный случай с одним элементом списка, который даст 3*n, что формально можно назвать и O(n*n*n), но так как там единица, то это чисто виртуальный куб.
Вы, похоже, не очень понимаете, что такое O().
3*n = O(n), а не O(n^3) *
O(n) - означает, что время работы в худшем случае (т.е. количество операций) алгоритма растет не быстрее линейного. Обычно считают худший случай, если не сказано специально, что это средняя оценка. Т.е. увеличели вы n в 10 раз - количество операций увеличилось не больше чем в 10 раз.
3*(n*10) = 10*(3*n) - количество операций увеличилось ровно в 10 раз. Тут O(n).
Для этого надо как-то оценить количество операций сверху. Иногда можно просто посчитать в лоб, иногда надо как-то что-то округлять. В этой задаче ограничение выводится просто: медленный указатель сделает не больше n шагов, быстрый сделает в 2 раза больше. Итого получается не больше 3n шагов. По идее надо еще считать все сравнения: цикл сделает по одному сравнению на каждую итерацию, которых не более n. Суммарно количество операций не более 4n. Обратите внимание, тут не считают какая операция медленная, а какая быстрая, может сравнение на самом деле это несколько операций: вычитание регистров и условный переход. Потому что в конце мы используем O(), которое константы отбрасывает и можно считать что все операции одинаково медленные.
будет O(k*n)
Что за k вообще? Если k - это константа, то она отбрасывается в O(). И остается O(n). В скобках должны остаться только параметры входных данных. Тут в задаче есть только n, поэтому в никаких других букв в оценку вставлять вообще не должны. У вас может быть O(n), O(n^10), O(2^n), O(log n), но никаких k там быть не должно.
даст 3*n, что формально можно назвать и O(n*n*n), но так как там единица, то это чисто виртуальный куб.
Как вы из 3n получили n^3 вообще непонятно. Что за единица, что за виртуальный куб?
*примечание
Формально n = O(n^3) и n = O(n^1000) - ибо эта запись означает оценку сверху, ограничение. Тут знак равенства вообще не является равенством в привычном смысле - это просто перегрузка нотации. Но принято использовать минимальную оценку, иначе смысла что-то оценивать вообще нет. Поэтому оценивать 3n как n*n*n - не правильно.
Вы, похоже, не очень понимаете, что такое O().
3*n = O(n), а не O(n^3) *
Я прекрасно понимаю что такое O().
Что за k вообще? Если k - это константа, то она отбрасывается в O()
Отбрасывайте, я не запрещаю, я лишь показываю что там нет n^2
Как вы из 3n получили n^3 вообще непонятно. Что за единица, что за виртуальный куб?
Поэтому оценивать 3n как n*n*n - не правильно.
Я знаю что O(1) и O(n) при n=1 это совсем не то же самое и сравнивать эти вещи не пытаюсь, но алгебраически 3*1 = 1^3 и вроде ничто не мешает использовать этот факт.
Вы написали "Не правда", не ясно к какой части цитаты это относится, к O(n) или к утверждению что указатели "пройдут по каждому элементу 1 раз".
Про O(n) я ответил, про "1 раз" я не комментировал. Но легко увидеть, что если кольцо сделать на элемент n/2+1 то указатели не встретятся и быстрый пробежит кольцо второй раз (что делает утверждение автора ошибочным), что даст k=2*n в любом случае.
А для какого цикла вы прогнозируете 3*n?
не ясно к какой части цитаты это относится
к " "пройдут по каждому элементу 1 раз". Извиняюсь за неточность.
А для какого цикла вы прогнозируете 3*n?
Для любого. Это оценка сверху. Худший случай будет, если цикл длины 1. Тогда медленный пройдет все вершины по 1 разу, а быстрый пройдет все вершины + последнюю еще n (или n-1) раз.
разбор баянистых элементарных задачек надо делать не так
а можно ваши регалии, чтобы понять кто указывает как надо, а как не надо?)
Переход на личности - лучший аргумент, да. /s
Могу предложить: медали с чемпионатов мира по программированию, PhD по computer science, преподавание в лагерях по подготовке школьников к олимпиадам по программированию, много лет проведения интервью в гугле, 1300 решенных задачек на литкоде. Еще что-то нужно, прежде чем вы даруете мне право критиковать статьи про задачки в интернете?
Заодно, не могли бы вы представить и ваши регалии, чтобы я мог понять, стоит ли на вас тратить время?
Буквально восприняли вопрос, не переходил на личности и не собирался, если так вышло - извиняюсь.
Вопрос был больше про - с чего вы решили, что вы лучше знаете как надо делать, а как не надо? И если вы знаете как надо, то делайте, приносите пользу)
Заодно, не могли бы вы представить и ваши регалии, чтобы я мог понять, стоит ли на вас тратить время?
не стоит)
О быстром и медленном указателях для этой задачи несколько раз писали на Хабре. Так же известно, что если стартовать два медленных указателя, один от начала списка, другой от места встречи fast и slow, то новая встреча будет как раз в узле, на который ссылается хвост. Доказательство этого факта внесло бы новизну в тему.
Насчет предложения - это будет в рамках другой задачи, где как раз нужно найти такой узел https://leetcode.com/problems/linked-list-cycle-ii/description/
указатели встретились на узле со значением 3, что указывает на наличие цикла.
Но ведь они встретились на узле 5. Вы же сами нарисовали это пошагово.
спасибо, исправил
А еще я не понял, неужели невозможен случай, когда быстрый указатель "перепрыгнет" медленный в цикле? Почему проверяется именно равенство?
если для одного круга перепрыгнет, то на каком-то другое круге они встретятся.
Если не равенство, то что проверить? элементы не отсортированы, количество мы не знаем
https://habr.com/ru/articles/853928/comments/#comment_27479330 - вот тут в комментарии дали ссылку на более продвинутое объяснение https://cp-algorithms.com/others/tortoise_and_hare.html
Не возможен. Если расписывать доказательство оценки по нормальному, то все видно. Когда медленный вступет на цикл, где-то там уже будет быстрый. И растояние между ними по кругу от быстрого будет L. За одну итерацию это растсояние увеличивается на 1 (медленный сделал шаг вперед) и уменьшается на 2 (быстрый его двумя шагами доганяет). Т.е. расстояние станет L+1-2 = L-1. Оно уменьшается на 1. И за ровно L итераций указатели встретятся - расстояние станет 0.
по нормальному
у каждого свое пониманиме нормального) дважды перечитал, что вы написал и ничего не понял
На каком предложении не понятно?
И растояние между ними по кругу от быстрого будет L. За одну итерацию это растсояние увеличивается на 1 (медленный сделал шаг вперед) и уменьшается на 2 (быстрый его двумя шагами доганяет). Т.е. расстояние станет L+1-2 = L-1. Оно уменьшается на 1. И за ровно L итераций указатели встретятся - расстояние станет 0.
Ну вот они на круге. Какое-то между ними расстояние есть (в смысле количество шагов по списку). Обозначим его L. Пока понятно? За одну итерацию цикла вы двигаете быстрый 2 раза, а медленный 1 раз. Как меняется расстояние между ними? Вспомните, что быстрый догоняет медленный - он сзади него. Медленный сделал шаг вперед - ушел вперед от медленного. Расстояние увеличилось на 1. Быстрый сделал 2 шага вперед - он догоняет медленный, расстояние на эти 2 шага уменьшилось. В итоге расстояние изменилось на -2+1= -1. Т.е. уменьшилось на 1. Так понятнее?
Решение задачи с собеседования Linked List Cycle [+ ВИДЕО]