Вряд ли это и для серверов также важно, как для лаптопов, но еще один важный фактор - перегрев. Когда процессор нагружен салобо, он может разгонять ядра. Когда работают все ядра, теплоотведение не справляется и всё начинает дико троттлить. И в итоге все N ядер суммарно выполняют меньше операций, чем когда было загружено N/2 ядер.
Небольшое замечание по оформлению: хабр поддерживает формулы в формате latex. В редакторе в меню + можно выбрать формулу. Получается что-то вроде этого:
Кое где в тексте вы это, похоже, даже используете. Если заменить на вот это вот ваши картинки с написанными от руки формулами, статья будет смотрется более представительно.
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 - не правильно.
Ну совсем без математики нельзя. Все-таки алгоритмы - это computer science, которая является областью математики. Ну можно хотя бы словами объяснить почти все.
Основная идея: когда медленный указатель зайдет на цикл, за одну итерацию расстояние между ними уменьшается на 1. В итоге за конечное число шагов (меньше длины цикла) быстрый указатель догонит медленного. Было между ними растояние L (если считать по циклу от быстрого), а стало L+1 - 2 = L-1 (+1 - медленный ушел вперед -2 - быстрый пошел вслед за ним). Поэтому, кастати, не надо проверять, не догнал ли быстрый указатель медленный дополнительно в середине его длинного шага - заяц через черепаху не перепрыгнет. Поэтому алгоритм рано или поздно остановится.
Еще можно было бы объяснять прогрессивно, по уровням, как до этого можно додуматься. Начнем с задачи проверить, является ли список замкнутым циклом, или линией вообще без циклов. Можно проверять одним указателем совпадение с перым элементом. Но если первый элемент не на цикле, то это не работает. Надо взять какой-то элемент в цикле. Но неизвестна же длина начала, поэтому нельзя сначала сделать много шагов, ибо неясно, а сколько их будет достаточно. Значит надо этот помеченный элемент в цикле двигать вперед. Но тогда сам указатель надо двигать на 2 шага, чтобы продвижение вперед, все-таки было.
И про время работы, если бы вы хотя бы примерно стали считать, а сколько там операций то происходит, то не ошиблись бы в рассуждениях.
надеюсь найдутся люди, для которых статья будет полезной)
Очень вряд ли. Вот так как вы объясняете - начинающим не понятно. Говорю как человек с опытом преподавания. Ваш текст вообще лишь дублирует код. Он должен объяснять не "что", а "как", "откуда" и "почему". Поскольку задача очень широко известная, то любой не совсем начинающий ее уже знает.
Соответственно, вам надо или задачи посложнее и не такие известные брать, или разъяснять почему вот это работает в тексте.
к " "пройдут по каждому элементу 1 раз". Извиняюсь за неточность.
А для какого цикла вы прогнозируете 3*n?
Для любого. Это оценка сверху. Худший случай будет, если цикл длины 1. Тогда медленный пройдет все вершины по 1 разу, а быстрый пройдет все вершины + последнюю еще n (или n-1) раз.
Могу предложить: медали с чемпионатов мира по программированию, PhD по computer science, преподавание в лагерях по подготовке школьников к олимпиадам по программированию, много лет проведения интервью в гугле, 1300 решенных задачек на литкоде. Еще что-то нужно, прежде чем вы даруете мне право критиковать статьи про задачки в интернете?
Заодно, не могли бы вы представить и ваши регалии, чтобы я мог понять, стоит ли на вас тратить время?
Там все еще будет O(n), потому что медленный указатель, действительно, пройдет по каждому элементу не более 1 раза (после того, как он ступит на цикл, быстрый догонит его раньше, чем он сделает полный круг). Быстрый делает 2 шага на 1 шаг медленного, поэтому общее количество ходов будет не больше 3n.
O(n), где n — количество элементов в списке, так как указатели проходят по каждому элементу максимум один раз.
Не правда. "Быстрый" указатель может по циклу сделать очень и очень много полных оборотов.
Ну и по статье - разбор баянистых элементарных задачек надо делать не так. Люди, которые их уже знают, от вашей статьи не получили ничего. Люди, которые их не умеют решать, от вашей статьи тоже не получили ничего, потому что им ничего не понятно. Максимум, что они тут могут сделать - это выучить код наизусть. Сомнительной полезности действие.
Вам надо не только приводить код решения (причем два раза: первый раз текстом, второй раз кодом), а объяснять, почему и как оно работает.
предполагается что количество ресурсов для одного разряда прямо пропорционально количеству цифр, что, конечно же, может не соответствовать действительности.
Ну вот вопрос, откуда вообще это предположение взялось-то? Причем оно появилось так явно, что аж целый термин "экономичность" ввели.
Конечно, лучше. Формулы от руки выглядят не серъезно.
Вряд ли это и для серверов также важно, как для лаптопов, но еще один важный фактор - перегрев. Когда процессор нагружен салобо, он может разгонять ядра. Когда работают все ядра, теплоотведение не справляется и всё начинает дико троттлить. И в итоге все N ядер суммарно выполняют меньше операций, чем когда было загружено N/2 ядер.
Не велика разница, все равно сумма растет экспоненциально в примерно 2 раза
Вот интересно, ограничение доступа к ютуб каналам со стороны гугла нарушает конституцию, а со стороны роскомпозора - нет.
Договор - это EULA ютуба, по которому он может вообще без объяснения причин удалить вообще все что угодно. И гугл ему и следовал, ничего не нарушая.
Небольшое замечание по оформлению: хабр поддерживает формулы в формате latex. В редакторе в меню + можно выбрать формулу. Получается что-то вроде этого:
Кое где в тексте вы это, похоже, даже используете. Если заменить на вот это вот ваши картинки с написанными от руки формулами, статья будет смотрется более представительно.
Особенно на квантовом уровне целые числа и есть. Электрон он либо есть, либо его нет. Общий зараяд - целое число в элементарных зарядах.
Четкой границы у макро объектов вроде и нет, но классы эквивалентности "принадлежит объекту X" вполне есть.
Так что за k? и как у вас там нет n^2, если ниже вы утверждаете, что там n^3? Хоть и "виртуальное"?
Что? 3*1 = 3. 1^3 = 1. 3!= 1
Вы, похоже, не очень понимаете, что такое 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(), которое константы отбрасывает и можно считать что все операции одинаково медленные.
Что за k вообще? Если k - это константа, то она отбрасывается в O(). И остается O(n). В скобках должны остаться только параметры входных данных. Тут в задаче есть только n, поэтому в никаких других букв в оценку вставлять вообще не должны. У вас может быть O(n), O(n^10), O(2^n), O(log n), но никаких k там быть не должно.
Как вы из 3n получили n^3 вообще непонятно. Что за единица, что за виртуальный куб?
*примечание
Формально n = O(n^3) и n = O(n^1000) - ибо эта запись означает оценку сверху, ограничение. Тут знак равенства вообще не является равенством в привычном смысле - это просто перегрузка нотации. Но принято использовать минимальную оценку, иначе смысла что-то оценивать вообще нет. Поэтому оценивать 3n как n*n*n - не правильно.
Ну совсем без математики нельзя. Все-таки алгоритмы - это computer science, которая является областью математики. Ну можно хотя бы словами объяснить почти все.
Основная идея: когда медленный указатель зайдет на цикл, за одну итерацию расстояние между ними уменьшается на 1. В итоге за конечное число шагов (меньше длины цикла) быстрый указатель догонит медленного. Было между ними растояние L (если считать по циклу от быстрого), а стало L+1 - 2 = L-1 (+1 - медленный ушел вперед -2 - быстрый пошел вслед за ним). Поэтому, кастати, не надо проверять, не догнал ли быстрый указатель медленный дополнительно в середине его длинного шага - заяц через черепаху не перепрыгнет. Поэтому алгоритм рано или поздно остановится.
Еще можно было бы объяснять прогрессивно, по уровням, как до этого можно додуматься. Начнем с задачи проверить, является ли список замкнутым циклом, или линией вообще без циклов. Можно проверять одним указателем совпадение с перым элементом. Но если первый элемент не на цикле, то это не работает. Надо взять какой-то элемент в цикле. Но неизвестна же длина начала, поэтому нельзя сначала сделать много шагов, ибо неясно, а сколько их будет достаточно. Значит надо этот помеченный элемент в цикле двигать вперед. Но тогда сам указатель надо двигать на 2 шага, чтобы продвижение вперед, все-таки было.
И про время работы, если бы вы хотя бы примерно стали считать, а сколько там операций то происходит, то не ошиблись бы в рассуждениях.
Например, тут: https://cp-algorithms.com/others/tortoise_and_hare.html
Например, тут: https://cp-algorithms.com/others/tortoise_and_hare.html
Очень вряд ли. Вот так как вы объясняете - начинающим не понятно. Говорю как человек с опытом преподавания. Ваш текст вообще лишь дублирует код. Он должен объяснять не "что", а "как", "откуда" и "почему". Поскольку задача очень широко известная, то любой не совсем начинающий ее уже знает.
Соответственно, вам надо или задачи посложнее и не такие известные брать, или разъяснять почему вот это работает в тексте.
к " "пройдут по каждому элементу 1 раз". Извиняюсь за неточность.
Для любого. Это оценка сверху. Худший случай будет, если цикл длины 1. Тогда медленный пройдет все вершины по 1 разу, а быстрый пройдет все вершины + последнюю еще n (или n-1) раз.
Потому что иначе в статье нет никакой пользы. Вы же зачем-то попытались аргументировать, почему там O(n) будет? Правда, с ошибкой.
Переход на личности - лучший аргумент, да. /s
Могу предложить: медали с чемпионатов мира по программированию, PhD по computer science, преподавание в лагерях по подготовке школьников к олимпиадам по программированию, много лет проведения интервью в гугле, 1300 решенных задачек на литкоде. Еще что-то нужно, прежде чем вы даруете мне право критиковать статьи про задачки в интернете?
Заодно, не могли бы вы представить и ваши регалии, чтобы я мог понять, стоит ли на вас тратить время?
Там все еще будет O(n), потому что медленный указатель, действительно, пройдет по каждому элементу не более 1 раза (после того, как он ступит на цикл, быстрый догонит его раньше, чем он сделает полный круг). Быстрый делает 2 шага на 1 шаг медленного, поэтому общее количество ходов будет не больше 3n.
Вот только это надо все расписать.
Не правда. "Быстрый" указатель может по циклу сделать очень и очень много полных оборотов.
Ну и по статье - разбор баянистых элементарных задачек надо делать не так. Люди, которые их уже знают, от вашей статьи не получили ничего. Люди, которые их не умеют решать, от вашей статьи тоже не получили ничего, потому что им ничего не понятно. Максимум, что они тут могут сделать - это выучить код наизусть. Сомнительной полезности действие.
Вам надо не только приводить код решения (причем два раза: первый раз текстом, второй раз кодом), а объяснять, почему и как оно работает.
Как администраторы, или как они там называются, должны понять, уволился ли он или нет? Обычно у людей нет доступа к рабочей почте после увольнения.
Кроме того, линус писал, что если предоставлят "достаточные документы", то восстановят.
Ну вот вопрос, откуда вообще это предположение взялось-то? Причем оно появилось так явно, что аж целый термин "экономичность" ввели.