Решение задач

Начните записывать мысли, чтобы усилить мышление. Этот совет я слышал много раз, но только в этом году решил сам попробовать. Результаты так впечатлили, что я решил описать опыт и поделиться теоретическими рассуждениями.

Что же я получил после полугода использования мышления письмом?

1. Я стал эффективнее при решении сложных задач. Раньше продумывание сложных задач требовало много времени и умственной энергии. Сейчас же исследования проходят быстрее, результат есть в документе, который я могу как сохранить для будущих рассуждений, так и как результат, который может служить частью отчёта. За счёт шаблонов решения более системны и продуманы.
2. Отвлечения перестали быть губительными. Раньше когда меня отвлекали, я терял последнюю цепочку рассуждений, поэтому приходилось продумывать часть заново. Во время прокрастинаций одни и те же мысли крутились по кругу. Сейчас я просто прочитаю последний абзац и в голове все мыслительные цепочки мгновенно восстанавливаются. Даже во время частых отвлечений мыслительная работа постепенно делается, а не буксует на месте.
3. После внедрения метода решения задач письмом на работе младший сотрудник стал более самостоятельным, так как он лучше понимает цели поставленной задачи, большинство вопросов отпадают на уровне формулировки в тексте. Лид может проследить цепочку рассуждений, что позволяет влиять не на результат, а на сам мыслительный процесс.
4. Стал чаще писать в корпоративную систему управления знаниями, стало понятнее как организовывать там материал.

Что с нашим обычным мышлением не так, что приходится выписывать рассуждения?

По закону Миллера мы можем держать в голове не более 7-и элементов. Обычно задачи сложнее, и в исследуемых системах гораздо больше 7-и элементов. Если перебираем различные варианты, то в мозгу сравниваются динамически создающиеся элементы, то будем постоянно упираться в этот предел.

Я у себя часто замечал, что при обдумывании различных вариантов решения, мозг быстро начинает захлебываться в количестве этих решений, и я начинаю возвращаться к решениям, которые думал несколько минут назад. После нескольких таких мыслительных циклов быстро приходит усталость. После отдыха удается продвинуться еще немного вперед, и снова устаешь. Не хочется обдумать одни и те же мысли по несколько раз и не тратить столько мыслительных ресурсов.

Когда нам нужно помнить о чем-то, то мозгу постоянно приходится возвращаться к этому. Представьте, что нас послали в магазин купить: молоко, хлеб, соль и фрукты. По пути в магазин нам постоянно нужно проигрывать этот список в голове, чтобы ничего не забыть: молоко, хлеб, соль и фрукты. Максим Дорофеев в своей книгу Джедайские техники написал, что каждая мысль, которая у нас крутится в голове, пожирает ресурсы организма (мыслетоплива). Если мы сможем вырастить привычки, которые позволят не запоминать, а записывать задачи, то сможем жить не только эффективнее, но и расслабленнее.

Наш мозг так устроен, что пытается увидеть смысл и историю в том, что он видит. Часто это работает, но иногда мы становимся жертвами натягивания реальности на идею. Психологи провели множество экспериментов на ложные воспоминания, в которых показали, что мозгу достаточно дать крупицы информации, по которым он может допридумать историю.

Элизабет Лофтус послала испытуемым буклеты из 4-х историй, записанные их родственниками. Среди этих 4-х историй одна история была вымышленной. Когда испытуемых попросили описать подробности событий, четверть из них смогла рассказать подробности и про вымышленную историю.

Это значит, что ощущения адекватности и рациональности наших мыслей ненадежны.

Как сделать так, чтобы

1. обойти проблему ограничения 7 плюс-минус 2,
2. не тратить ресурсы на содержание идей в голове,
3. не дать мозгу обманывать нас?

Оказывается есть универсальное простое решение, которое заключается в том, что нужно использовать внешние источники фиксирования мыслей.

Рассмотрим эту идею на примере шахмат (пример взят из курса Образование для образованных 2020). Опытные шахматисты умеют играть в шахматы в уме, то есть не используя физические фигуры и поле. Это называется играть вслепую. Но

1. так умеют играть только опытные шахматисты,
2. а при игре двух одинаковых по силе шахматистов, когда один играет вслепую, а другой видит позицию на доске, с легкостью побеждает второй.

Почему играть вслепую сложнее? Второму шахматисту не нужно тратить мыслетопливо для того, чтобы держать позицию в голове. Вместо этого он смотрит на фигуры, на поле и быстро переключает внимание между различными комбинациями. Это и есть концепция экзокортекса вынести за пределы мозга все, что позволяет облегчить решение задач.

Если для игры в шахматы экзокортексом служат фигуры и поле, то для остальных процессов могут использоваться текст, псевдокод или программный код, визуальные языки моделирования, графы, рисунки все зависит от процесса, который вы хотите вынести из мозга.

Мышление письмом является наиболее универсальным способом вынесения мыслей из головы. В большинстве случаев этот способ и наиболее эффективный. Написать связанный текст сложнее, чем нарисовать несколько квадратиков и связать их линиями или выписать идеи в буллеты.

Три примера из разных областей, в которых мышлением письмом показало свою эффективность

Пример 1. Улучшение психологического благосостояния

Однажды James Pennebaker узнал, что когда люди рассказывают про свое горе другим людям, то они быстрее восстанавливаются. James задумался о том, будет ли такой же эффект, если люди будут описывать свое горе в тексте. Оказалось, что так тоже работает. В дальнейшем было показано, что также хорошо работает письменно отвечать на вопросы, связанные с будущими планами.

В другом эксперименте испытуемых студентов попросили подумать о планах на несколько лет вперед. Одну группу попросили визуализировать, как будто те добиваются своих целей, а вторую группу попросили письменно расписать шаги по воплощению своих планов. В конце года у второй группы средний балл повысился.

Письменная проработка целей положительно влияет не только на области, на которые есть планы, то есть эффект оказывается обобщается между различными сферами жизни.

В проекте Self Authoring в треке Future Authoring клиентам предлагается сформулировать несколько целей на 3-5 лет вперед. Затем по каждой цели просят письменно описать жизнь через 3-5 лет, если эта цель будет полностью выполнена, а также противоположный вариант, когда эта цель не будет выполнена совсем. Таким образом формируется вектор, который направленный к выполнению цели.

Теперь каждый раз, когда клиент будет последовательно или случайно приближаться к своей цели, то есть двигаться по сформулированному вектору, мозг будет вырабатывать дофамин, другими словами радоваться. Важно, что такой вектор в голове не формируется, если это упражнение провести в уме, нужно именно выписать идеи в текст!

Один из авторов проекта Jordan Peterson утверждает, что просто наличие таких векторов в голове людей делает их счастливыми.

Пример 2. Масштабируемый менеджмент

Основатель Амазона, Джефф Безос считает, что главная причина успешной организации это масштабируемый менеджмент. Масштабируемость менеджмента в Amazon обеспечивается тем, что менеджеры обязаны написать 6-и страничный документ на каждое важное решение, которое требуется принять. Нельзя просто созвать коллег, показать презентацию и принять решение. Презентации запрещены в Амазоне.

Вместо этого автор документа распечатывает документ в самом начале встречи и раздает всем слушателям. Первые 15 минут все в тишине читают документ, делают пометки на полях, подчеркивают непонятные места. Затем 20 минут презентующий пробегается по каждому абзацу с ручкой в руке и спрашивает комментарии у слушателей, убеждается, что все одинаково понимают документ. Затем 20 минут идет обсуждение и принятие решения. Последние 5 минут встречи фиксируются принятые решения. Документ можно сократить до 2 страниц, если вопрос простой, тогда все минуты нужно просто поделить на 3. Если же документ получается более 6 страниц, то считается, что вопрос слишком сложный, поэтому его нужно разбить на несколько частей и решить в несколько встреч.

Каким образом такой документ масштабирует менеджмент? Andy Grove, бывший CEO Intel и автор High Output Management, считает, что ценность таких документов не в чтении, а в написании. Лучше менеджер потратит больше времени на написание и обдумывание документа, чем потом исполнители будут решать проблемы, возникшие из-за непродуманных моментов.

Существует свод правил, которым должен подчиняться документ. Эти правила как раз составляют масштабируемость правильного образа мыслей.

• Документ должен иметь цель. Все, что не касается текущей цели должны быть вынесены в отдельные документы.
• В документе менеджер должен показать, что думает за клиента и о клиенте. У продуктовых менеджеров Амазон существует прием working backwards, когда сначала пишется пресс-релиз с описание якобы уже созданного продукта с цитатами клиентов о том, как продукт помогает им в жизни.
• Документ должен затрагивать большую картину организации.
• В документе запрещено быть эмоциональным. Вместо большинство пользователей рекомендуется указать точное число, например 55.7% пользователей.
• В документе должно быть проанализировано не менее двух различных решений. Лучше больше.

Существует этикет поведения на встречах. Вот некоторые правила оттуда:

• Будь готов поменять свою точку зрения на встрече.
• Если не успел подготовить текст к встрече, то лучше отодвинуть встречу и взять время на подготовку, чем провести плохую встречу.
• Если начальник не согласен, но у тебя недостаёт данных, попроси следующую встречу, где ты сможешь подготовиться лучше.

Такой формат ведения встреч обладает следующими преимуществами:

• Удобно для читателей, сложно для писателей, что делает процесс принятия решения более продуманным, а количество неэффективных встреч уменьшается.
• Встреча превращается в общение, а не монолог выступающего.
• Если обычно интроверты страдают на встречах, то здесь они могут сосредоточиться на проблеме, а не эффектном донесении. Теперь задавить коллег просто уверенностью стало сложнее.
• После встречи остается документ, который в последующем служит материалом для принятия решения.
• Этот документ можно использовать для анализа принципов мышления автора.

Такой документ и способ ведения встреч не сразу появился в Амазоне. Например, в начале документ выдавался менеджерам до встречи, чтобы те приходили на встречи подготовленными, но со временем Безос заметил, что даже самые крутые топ-менеджеры приходят непрочитавшими документ, а обсуждение они начинали просто пробежавшись по тексту за 5 минут до встречи. Тогда было решено не бороться с таким поведением, а выделить первую часть встречи на ознакомление.

Этот документ впечатлил меня так, что я решил сделать похожий документ в компании, в которой работаю.

Пример 3. Решение исследовательских задач отдела RnD

За время работы главой отдела RnD во Flocktory ^{[ссылка удалена модератором]} я заметил несколько проблем, которые мне показалось возможным решить с помощью мышления письмом.

1. Некоторые задачи бывают слишком сложными, чтобы можно было порисовать и придумать решение. Даже если решение придумано, то проработка деталей с одновременным удержанием в голове ещё нереализованного решений требует сильного напряжения. Иногда начинается пробуксовка и перепродумывание одного и того же, о чем я писал в начале статьи.
2. Не всегда в задачах прописываются все требования, исполнители не всегда задумываются о том, что написано в требованиях. Например, дата сайентист испытывает сильное искушение, когда есть намек, что задачу можно решить с помощью машинного обучения.
3. Исполнитель не выделяет время, чтобы отметить окончание работы.

В июле мы внедрили мышление письмом для решения сложных задач. По сути это просто шаблон, состоящий из трех глав, которые нужно заполнять во время решения задачи.

1. Начинаем с выписывания целей задачи своими словами, как решение должно повлиять на ключевые метрики компании. Эта глава заставляет исполнителя посмотреть на свою задачу глазами бизнеса.

2. Затем следует основная глава, где исполнитель записывает свои размышления и тут же проверяет гипотезы. Текст в этом разделе должен содержать словосочетания, намекающие на работу мышления: из это следует, но, следует, гипотеза, проверка, опровергает, подтверждает и т.д. В этой главе происходит магия мышления письмом.

3. После выполнения задачи исполнителю предлагается выписать

• все результаты отдельным списком,
• подумать о том, что можно поменять в организации, чтобы такие задачи не возникали или решались быстрее,
• (мой любимый раздел) чему научился исполнитель во время выполнения задачи.

Чтобы документ легче читался другими людьми или самим исполнителем через большой промежуток времени (по сути тоже другой человек), второй раздел располагается в самом конце документа.

Такой формат решения подходит далеко не для каждой задачи, только 30% времени работы уходит на решение задач таким образом. Основная причина в том, что написание текста требует много времени. Когда не нужно решать задачу письмом:

• задача простая
• известен алгоритм решения задачи
• нужно написать программу по четкому ТЗ (при программировании автоматически включается мышление кодом), мышление письмом скорее нужно для написания ТЗ.
• решить задачу можно быстрым созвоном.

Как начать практиковать мышление письмом?

В следующий раз, когда столкнетесь со сложной задачей, начните записывать цепочку рассуждений в тексте. Это не так просто из-за того, потому что очень неприятно осознавать, что идея, которая казались такой понятной, в тексте оказывается несвязанными и невнятными тезисами, сразу возникает желание бросить все это. У меня первое время записывание мыслей вызывало физический дискомфорт, желание заняться делом, не тратить время на ерунду. Но постепенно это чувство пропало, а записывание превратилось в привычку.

Ещё одним способом практикования мышление письмом является ведение блога, это позволяет осмысливать идеи, которые вы собрали по интересной для вас теме. Чтобы проверить способ, я неделю назад начал блог в телеграме про мышление. Вторая цель блога собрать сообщество людей, которым интересно работать над улучшением своего мышления.

Заключение

Мышление письмом заставляет писателя лучше продумывать мысли, в тексте становятся заметны туманные участки рассуждения. Этот текст в дальнейшем может служить корпоративным документом для обсуждения, временным местом для хранения цепочек рассуждения, а также способом увидеть как мыслит исполнитель. Мозг больше доверяет написанному, чем продуманному, поэтому мышление письмом обладает психотерапевтическими свойствами.

В этой статье мы рассмотрели влияние написания текста на мышление в процессе. Но мы не рассмотрели другую очевидную функцию текста сохранение информации. Никлас Люман создал методику написания книг и статей, известную как Zettelkasten, благодаря которой он написал 58 книг, более 100 статей. Эта методика переворачивает процесс написания текста. Если классический способ написания книг напоминает водопадную модель разработки: цель, планы, выполнение, то Люман писал маленькие заметки в моменты, когда его посещала мысль. Когда заметок на одну тему становилось достаточное количество, эти заметки объединялись в книги напоминает гибкий способ разработки. Кстати, настоящая статья была написана именно таким способом!

В век информационных технологий и автоматизации работа над своим мышлением дает человеку конкурентное преимущество. Думаю, что интерес к этой теме будет только возрастать. Мышление письмом эффективный и доступный инструмент, который можно начать применять сразу, после прочтения этой статьи.

Очень часто авторы алгоритмических задач делают ход конём: они берут задачу с простыми формулировками, заменяют их сложными и непонятными эквивалентами и выдают вам сложную задачу. В этом посте мы разберём пример одной такой задачи и обсудим пару полезных для её решения приёмов. Задача будет про палиндром.



Продолжение под катом.

Что такое палиндром

Палиндромом называется строка, которая одинаково читается как слева направо, так и справа налево. Например, слово АТАТА это палиндром, а вот слово АЙАЙАЙ нет.


Пример палиндрома из латинских слов: он составлен таким образом, что в каком бы направлении вы ни начали читать текст, получится одно и то же

Известный кинематографический палиндром название вышедшего в 2020 году фильма Довод (англ. Tenet). Русская адаптация в каком-то плане уникальна, потому что у нас нашлась подходящая альтернатива слову tenet, которая тоже является палиндромом. На многих других языках (в том числе славянских) название фильма оставили как есть. Например, на украинском это ТЕНЕТ (Википедия).

Постановка задачи

Итак, задача. Подготовьтесь морально.

Нечётным палиндромом будем называть такую строку, у которой все подстроки нечётной длины являются палиндромами. Суть задачи в том, чтобы в данной строке заменить не более K символов так, чтобы максимизировать длину самой длинной подстроки, которая является нечётным палиндромом.

Всё, клубок запутался. Начнём распутывать.

Вот несколько примеров нечётных палиндромов: ATATA, KKKKKKKK, ABA, ZO.

Рассмотрим подробнее первую строку АТАТА. Выпишем все её подстроки нечётной длины:

• A, T, A, T, A однобуквенное слово всегда палиндром
• ATA, TAT, ATA очевидно, палиндромы
• ATATA тоже

В слове ZO нет подстрок нечётной длины больше чем в одну букву. И Z, и O палиндромы, поэтому ZO нечётный палиндром.

Пусть нам дана строка ABCDEF, и мы можем заменить не более одного символа (K=1), чтобы сделать из неё нечётный палиндром. Оптимальным решением было бы, например, заменить первую букву на C, тогда мы получили бы CBCDEF, где длина наибольшей подстроки, являющейся нечётным палиндромом, была бы равна трём (это CBC).

С тем же успехом мы могли бы прийти к варианту ABCFEF.

А вот если изначально у нас была строка ZXXXZ, и опять можно изменить не более одного символа, то надо заменить средний, так как ZXX и XXZ не являются палиндромами. В итоге мы получим ZXZXZ.

Структура нечётного палиндрома

Теперь заметим кое-что в рассмотренных примерах. Все нечётные палиндромы имеют схожую структуру: в них чередуются буквы (или все буквы одинаковые). И это действительно единственная форма, которую имеет нечётный палиндром. Почему это так?

Посмотрим ещё раз на определение: нечётным палиндромом будем называть такую строку, у которой все подстроки нечётной длины являются палиндромами. Если все подстроки нечётной длины являются палиндромами, то и все подстроки длины 3 являются палиндромами. Отсюда сразу же следует, что на чётных позициях не может быть двух различных букв, то же самое верно для нечётных.


На рисунке выше показано, как получается чередующаяся структура строки. Одинаковым цветом выделены одинаковые символы. Сначала посмотрим на палиндром длины 3, который начинается в самом первом символе исходной строки. Тогда 1 и 3 символ можно пометить зеленым. Про 2-й символ пока ничего непонятно. Сдвинем палиндром на единицу вправо, получим, что 2 и 4 символы можно покрасить в один цвет. Так, сдвигаясь каждый раз на единицу, мы получим, что все символы на нечётных позициях зелёные, а на чётных синие. Более строго можно доказать этот факт с помощью метода математической индукции, например.

Теперь, когда мы поняли, что надо искать, вернёмся непосредственно к задаче. Для краткости будем называть подстроки, которые являются нечётными палиндромами, хорошими. Надо изменить не более K символов так, чтобы максимизировать длину хорошей подстроки в последовательности.

Сперва разберёмся, как сделать из произвольной подстроки хорошую. Надо заменить на один и тот же символ все элементы на чётных позициях и отдельно заменить на нечётных.

Чтобы сделать как можно меньше замен, стоит выбрать в качестве единого символа самый частый среди тех, что стоят на чётных или нечётных позициях. Найти самый частый символ можно с помощью словаря (хеш-мапа, хеш-таблицы) отдельно для чётных и нечётных позиций. Алфавит в текущей задаче ограничен 26 символами, поэтому счётчик будет занимать константное количество дополнительной памяти.

Пройдёмся один раз по строке и добавим единицу в ячейку нужного словаря по текущему символу. Далее найдём в каждом словаре самый частый символ (если символов с максимальным числом вхождений несколько, то можно выбрать любой). Именно на этот символ надо заменить все элементы на чётных или нечётных позициях.

Наивное решение

Теперь попробуем сделать как можно более длинную хорошую подстроку, которая начинается строго в символе с номером L. Указатель R будет отмечать ту позицию, до которой мы сумели расширить хорошую подстроку. Будем шагать указателем R вправо, начиная от позиции L. На каждом шаге будем учитывать в счётчике символов для чётных и нечётных позиций очередной символ. Прежде чем передвинуть R на шаг вправо, проверим по счётчикам, что сделать подстроку с L до R хорошей можно не более чем за K операций.

Если применить описанные действия независимо для всех L от 0 до n 1, где n длина исходной строки, а затем найти наиболее длинную найденную хорошую подстроку, то мы решим задачу. Однако временная сложность данного решения составит O(n^2), так как для каждой позиции L мы сделаем в худшем случае примерно n L шагов при передвижении R.

Улучшаем асимптотику решения

Мы можем ускорить это решение с помощью техники двух указателей. Не будем обнулять счётчики и сбрасывать позицию R после того, как максимально отошли вправо от L. Переиспользуем текущую информацию при переходе от L к L+1. Для этого надо убрать из счётчиков элемент на позиции L и всё. Затем можно продолжать делать проверки и отодвигать R вправо до тех пор, пока не исчерпаются K операций изменения элементов.


На рисунке выше показан ход указателей L и R, K=2. Подчёркнутые символы будут изменены при соответствующих L и R

Оценим сложность новой версии алгоритма. Указатель R суммарно сделает не более n шагов вправо, указатель L тоже. Передвижение указателя сопровождается обновлением счётчиков и проверкой числа изменений для получения хорошей подстроки эти действия выполняются за константное время, O(1). Таким образом мы получаем сложность O(n).

Мы выпутались из этой задачи, теперь можно запутываться в какую-нибудь другую.

Подробнее про метод двух указателей и про другие интересные приёмы мы рассказываем на курсе Алгоритмы и структуры данных. Если вам интересна эта тема, приглашаю на наш курс.

Добрый день. Сегодня хочется поговорить о том, как найти MEX (минимальное отсутствующие число во множестве).


Мы разберем три алгоритма и посмотрим на их производительность.

Добро пожаловать под cat

Предисловие

Перед тем как начать, хотелось бы рассказать почему я вообще за этот алгоритм взялся?
Всё началось с задачки на OZON.


Как видно из задачи, в математике результатом работы функции MEX на множестве чисел является наименьшим значением из всего набора, который не принадлежит этому множеству. То есть это минимальное значение набора дополнений. Название MEX является сокращением для Minimum EXcluded значение.

И покопавшись в сети, оказалось, что нет общепринятого алгоритма нахождения MEX

Есть решения в лоб, есть варианты с дополнительными массивами, графами, но, как-то всё это раскидано по разным углам интернета и нет единой нормальной статьи по этому поводу. Вот и родилась идея написать эту статью. В этой статье мы разберем три алгоритм нахождения MEX и посмотрим, что у нас получиться по скорости и по памяти.
Код будет на языке C#, но в целом там не будет специфичных конструкций.
Базовый код для проверок будет таким.

static void Main(string[] args)        {            //MEX = 2            int[] values = new[] { 0, 12, 4, 7, 1 };                        //MEX = 5            //int[] values = new[] { 0, 1, 2, 3, 4 };                        //MEX = 24            //int[] values = new[] { 11, 10, 9, 8, 15, 14, 13, 12, 3, 2, 0, 7, 6, 5, 27, 26, 25, 4, 31, 30, 28, 19, 18, 17, 16, 23, 22, 21, 20, 43, 1, 40, 47, 46, 45, 44, 35, 33, 32, 39, 38, 37, 36, 58, 57, 56, 63, 62, 60, 51, 49, 48, 55, 53, 52, 75, 73, 72, 79, 77, 67, 66, 65, 71, 70, 68, 90, 89, 88, 95, 94, 93, 92, 83, 82, 81, 80, 87, 86, 84, 107, 106, 104 };                        //MEX = 1000            //int[] values = new int[1000];            //for (int i = 0; i < values.Length; i++) values[i] = i;                        //Импровизированный счетчик итераций            int total = 0;            int mex = GetMEX(values, ref total);            Console.WriteLine($"mex: {mex}, total: {total}");            Console.ReadKey();        }

И еще один момент в статье я часто упоминаю слово массив, хотя более правильным будет множество, то заранее хочу извиниться перед теми, кому будет резать слух данное допущение.

1) Решение в лоб

Как нам найти минимальное отсутствующие число? Самый простой вариант сделать счетчик и перебирать массив до тех пор, пока не найдем число равное счетчику.

  static int GetMEX(int[] values, ref int total)        {            for (int mex = 0; mex < values.Length; mex++)            {                bool notFound = true;                for (int i = 0; i < values.Length; i++)                {                    total++;                    if (values[i] == mex)                    {                        notFound = false;                        break;                    }                }                if (notFound)                {                    return mex;                }            }            return values.Length;        }    }

Максимально базовый случай. Сложность алгоритма составляет O(n*cell(n/2)) Т.к. для случая { 0, 1, 2, 3, 4 } нам нужно будет перебрать все числа т.к. совершить 15 операций. А для полностью заполного ряда из 100 числе 5050 операций Так себе быстродейственность.

2) Просеивание

Второй по сложности вариант в реализации укладывается в O(n) Ну или почти O(n), математики хитрят и не учитывают подготовку данных Ибо, как минимум, нам нужно знать максимальное число во множестве.
С точки зрения математики выглядит так.
Берется битовый массив S длинной m (где m максимально число в изначально массиве (V) + 1) заполненный 0. И в один проход исходному множеству (V) в массиве (S) ставятся 1. После этого в один проход находим первое пустое значение.

static int GetMEX(int[] values, ref int total)        {            //Не учитываем в сложности             var max = values.Max() + 1;            bool[] sieve = new bool[max];            for (int i = 0; i < values.Length; i++)            {                total++;                sieve[values[i]] = true;            }            for (int i = 0; i < sieve.Length; i++)            {                total++;                if (!sieve[i])                {                    return i;                }            }            return values.Length;        }

Т.к. математики хитры люди. То они говорят, что алгоритм O(n) ведь проход по массиву исходному массиву всего один
Т.к. математики хитры люди. И говорят, что алгоритм O(n) ведь проход по массиву исходному массиву всего один
Вот сидят и радуются, что такой крутой алгоритм придумали, но правда такова.
Первое нужно найти максимально число в исходном массиве O1(n)
Второе нужно пройтись по исходному массиву и отметить это значение в массиве S O2(n)
Третье нужно пройтись массиве S и найти там первую попавшеюся свободную ячейку O3(n)
Итого, т.к. все операции в целом не сложные можно упростить все расчеты до O(n*3)
Но это явно лучше решения в лоб Давайте проверим на наших тестовых данных:
1) Для случая { 0, 12, 4, 7, 1 }: В лоб: 11 итераций, просеивание: 13 итераций
2) Для случая { 0, 1, 2, 3, 4 }: В лоб: 15 итераций, просеивание: 15 итераций
3) Для случая { 11,}: В лоб: 441 итерация, просеивание: 191 итерация
4) Для случая { 0,,999}: В лоб: 500500 итераций, просеивание: 3000 итераций

Дело в том, что если отсутствующие значение является небольшим числом, то в таком случае решение в лоб оказывается быстрее, т.к. не требует тройного прохода по массиву. Но в целом, на больших размерностях явно проигрывает просеиванью, что собственно неудивительно.
С точки зрения математика алгоритм готов, и он великолепен, но вот с точки зрения программиста он ужасен из-за объема оперативной памяти, израсходованной впустую, да и финальный проход для поиска первого пустого значения явно хочется ускорить.
Давайте сделаем это, и оптимизируем код.

static int GetMEX(int[] values, ref int total)        {            total = values.Length;            var max = values.Max() + 1;            var size = sizeof(ulong) * 8;            ulong[] sieve = new ulong[(max / size) + 1];            ulong one = 1;            for (int i = 0; i < values.Length; i++)            {                total++;                sieve[values[i] / size] |= (one << (values[i] % size));            }            var maxInblock = ulong.MaxValue;            for (int i = 0; i < sieve.Length; i++)            {                total++;                if (sieve[i] != maxInblock)                {                    for (int j = 0; j < size; j++)                    {                        total++;                        if ((sieve[i] & (one << j)) == 0)                        {                            return i * size + j;                        }                    }                }            }            return values.Length;        }

Что мы тут сделали. Во-первых, в 64 раза уменьшили количество оперативной памяти, которая необходима.

var size = sizeof(ulong) * 8;ulong[] sieve = new ulong[(max / size) + 1];

Во-вторых, оптимизировали фальную проверку: мы проверяем сразу блок на вхождение первых 64 значений: if (sieve[i] != maxInblock) и как только убедились в том, что значение блока не равно бинарным 11111111 11111111 11111111 11111111 11111111 11111111 11111111 11111111, только тогда ищем уже вхождение на уровне блока: ((sieve[i] & (one << j)) == 0
В итоге алгоритм просеивание нам дает следующие результат:
1) Для случая { 0, 12, 4, 7, 1 }: просеивание: 13 итераций, просеивание с оптимизацией: 13 итераций
2) Для случая { 0, 1, 2, 3, 4 }: В лоб: 15 итераций, просеивание с оптимизацией: 16 итераций
3) Для случая { 11,}: В лоб: 191 итерация, просеивание с оптимизацией: 191 итерации
4) Для случая { 0,,999}: В лоб: 3000 итераций, просеивание с оптимизацией: 2056 итераций

Так, что в итоге в теории по скорости?
O(n*3) мы превратили в O(n*2) + O(n / 64) в целом, чуть увеличили скорость, да еще объём оперативной памяти уменьшили аж в 64 раза. Что хорошо)

3) Сортировка

Как не сложно догадаться, самый простой способ найти отсутствующий элемент во множестве это иметь отсортированное множество.
Самый быстрый алгоритм сортировки это quicksort (быстрая сортировка), которая имеет сложность в O1(n log(n)). И итого мы получим теоретическую сложность для поиска MEX в O1(n log(n)) + O2(n)

static int GetMEX(int[] values, ref int total)        {            total = values.Length * (int)Math.Log(values.Length);            values = values.OrderBy(x => x).ToArray();            for (int i = 0; i < values.Length - 1; i++)            {                total++;                if (values[i] + 1 != values[i + 1])                {                    return values[i] + 1;                }            }            return values.Length;        }

Шикарно. Ничего лишнего)
Проверим количество итераций
1) Для случая { 0, 12, 4, 7, 1 }: просеивание с оптимизацией: 13, сортировка: ~7 итераций
2) Для случая { 0, 1, 2, 3, 4 }: просеивание с оптимизацией: 16 итераций, сортировка: ~9 итераций
3) Для случая { 11,}: просеивание с оптимизацией: 191 итерации, сортировка: ~356 итераций
4) Для случая { 0,,999}: просеивание с оптимизацией: 2056 итераций, сортировка: ~6999 итераций

Здесь указаны средние значения, и они не совсем справедливы. Но в целом: сортировка не требует дополнительной памяти и явно позволяет упростить последний шаг в переборе.
Примечание: values.OrderBy(x => x).ToArray() да я знаю, что тут выделилась память, но если делать по уму, то можно изменить массив, а не копировать его


Вот у меня и возникла идея оптимизировать quicksort для поиска MEX. Данный вариант алгоритма я не находил в интернете, ни с точки зрения математики, и уж тем более с точки зрения программирования. То код будем писать с 0 по дороге придумывая как он будет выглядеть :D

Но, для начала, давайте вспомним как вообще работает quicksort. Я бы ссылку дал, но нормально пояснения quicksort на пальцах фактически нету, создается ощущение, что авторы пособий сами разбираются в алгоритме пока его рассказывают про него
Так вот, что такое quicksort:
У нас есть неупорядоченный массив { 0, 12, 4, 7, 1 }
Нам потребуется случайное число, но лучше взять любое из массива, это называется опорное число (T).
И два указателя: L1 смотрит на первый элемент массива, L2 смотрит на последний элемент массива.
0, 12, 4, 7, 1
L1 = 0, L2 = 1, T = 1 (T взял тупа последние)

Первый этап итерации:
Пока работам только с указателем L1
Сдвигаем его по массиву вправо пока не найдем число больше чем наше опорное.
В нашем случае L1 равен 8

Второй этап итерации:
Теперь сдвигаем указатель L2
Сдвигаем его по массиву влево пока не найдем число меньше либо равное чем наше опорное.
В данном случае L2 равен 1. Т.к. я взял опорное число равным крайнему элементу массива, а туда же смотрел L2.

Третей этап итерации:
Меняем числа в указателях L1 и L2 местами, указатели не двигаем.
И переходим к первому этапу итерации.
Эти этапы мы повторяем до тех пор, пока указатели L1 и L2 не будет равны, не значения по ним, а именно указатели. Т.е. они должны указывать на один элемент.

После того как указатели сойдутся на каком-то элементе, обе части массива будут всё еще не отсортированы, но уже точно, с одной стороны объеденных указателей (L1 и L2) будут элементы, которые меньше T, а со второй больше T. Именно этот факт нам и позволяет разбить массив на две независимые группы, которые мы сортируем можно сортировать в разных потоках в дальнейших итерациях.
Статья на wiki, если и у меня непонятно написанно

Напишем Quicksort

static void Quicksort(int[] values, int l1, int l2, int t, ref int total)        {            var index = QuicksortSub(values, l1, l2, t, ref total);            if (l1 < index)            {                Quicksort(values, l1, index - 1, values[index - 1], ref total);            }            if (index < l2)            {                Quicksort(values, index, l2, values[l2], ref total);            }        }        static int QuicksortSub(int[] values, int l1, int l2, int t, ref int total)        {            for (; l1 < l2; l1++)            {                total++;                if (t < values[l1])                {                    total--;                    for (; l1 <= l2; l2--)                    {                        total++;                        if (l1 == l2)                        {                            return l2;                        }                        if (values[l2] <= t)                        {                            values[l1] = values[l1] ^ values[l2];                            values[l2] = values[l1] ^ values[l2];                            values[l1] = values[l1] ^ values[l2];                            break;                        }                    }                }            }            return l2;        }

Проверим реальное количество итераций:
1) Для случая { 0, 12, 4, 7, 1 }: просеивание с оптимизацией: 13, сортировка: 11 итераций
2) Для случая { 0, 1, 2, 3, 4 }: просеивание с оптимизацией: 16 итераций, сортировка: 14 итераций
3) Для случая { 11,}: просеивание с оптимизацией: 191 итерации, сортировка: 1520 итераций
4) Для случая { 0,,999}: просеивание с оптимизацией: 2056 итераций, сортировка: 500499 итераций

Попробуем поразмышлять вот над чем. В массиве { 0, 4, 1, 2, 3 } нет недостающих элементов, а его длина равно 5. Т.е. получается, массив в котором нет отсутствующих элементов равен длине массива 1. Т.е. m = { 0, 4, 1, 2, 3 }, Length(m) == Max(m) + 1. И самое главное в этом моменте, что это условие справедливо, если значения в массиве переставлены местами. И важно то, что это условие можно распространить на части массива. А именно вот так:
{ 0, 4, 1, 2, 3, 12, 10, 11, 14 } зная, что в левой части массива все числа меньше некого опорного числа, например 5, а в правой всё что больше, то нет смысла искать минимальное число слева.
Т.е. если мы точно знаем, что в одной из частей нет элементов больше определённого значения, то само это отсутствующие число нужно искать во второй части массива. В целом так работает алгоритм бинарного поиска.
В итоге у меня родилась мысль упростить quicksort для поиска MEX объединив его с бинарным поиском. Сразу скажу нам не нужно будет полностью отсортировывать весь массив только те части, в которых мы будем осуществлять поиск.
В итоге получаем код

static int GetMEX(int[] values, ref int total)        {            return QuicksortMEX(values, 0, values.Length - 1, values[values.Length - 1], ref total);        }        static int QuicksortMEX(int[] values, int l1, int l2, int t, ref int total)        {            if (l1 == l2)            {                return l1;            }            int max = -1;            var index = QuicksortMEXSub(values, l1, l2, t, ref max, ref total);            if (index < max + 1)            {                return QuicksortMEX(values, l1, index - 1, values[index - 1], ref total);            }            if (index == values.Length - 1)            {                return index + 1;            }            return QuicksortMEX(values, index, l2, values[l2], ref total);        }        static int QuicksortMEXSub(int[] values, int l1, int l2, int t, ref int max, ref int total)        {            for (; l1 < l2; l1++)            {                total++;                if (values[l1] < t && max < values[l1])                {                    max = values[l1];                }                if (t < values[l1])                {                    total--;                    for (; l1 <= l2; l2--)                    {                        total++;                        if (values[l2] == t && max < values[l2])                        {                            max = values[l2];                        }                        if (l1 == l2)                        {                            return l2;                        }                        if (values[l2] <= t)                        {                            values[l1] = values[l1] ^ values[l2];                            values[l2] = values[l1] ^ values[l2];                            values[l1] = values[l1] ^ values[l2];                            break;                        }                    }                }            }            return l2;        }

Проверим количество итераций
1) Для случая { 0, 12, 4, 7, 1 }: просеивание с оптимизацией: 13, сортировка MEX: 8 итераций
2) Для случая { 0, 1, 2, 3, 4 }: просеивание с оптимизацией: 16 итераций, сортировка MEX: 4 итераций
3) Для случая { 11,}: просеивание с оптимизацией: 191 итерации, сортировка MEX: 1353 итераций
4) Для случая { 0,,999}: просеивание с оптимизацией: 2056 итераций, сортировка MEX: 999 итераций

Итого

Мы получили разны варианты поиска MEX. Какой из них лучше решать вам.
В целом. Мне больше всех нравится просеивание, и вот по каким причинам:
У него очень предсказуемое время выполнения. Более того, этот алгоритм можно легко использовать в многопоточном режиме. Т.е. разделить массив на части и каждую часть пробегать в отдельном потоке:

for (int i = minIndexThread; i < maxIndexThread; i++)sieve[values[i] / size] |= (one << (values[i] % size));

Единственное, нужен lock при записи sieve[values[i] / size]. И еще алгоритм идеален при выгрузки данных из базы данных. Можно грузить пачками по 1000 штук например, в каждом потоке и всё равно он будет работать.
Но если у нас строгая нехватка памяти, то сортировка MEX явно выглядит лучше.

П.с.
Я начал рассказ с конкурса на OZON в котором я пробовал участвовал, сделав предварительный вариант алгоритма просеиванья, приз за него я так и не получил, OZON счел его неудовлетворительным По каким именно причин он так и не сознался До и кода победителя я не видел. Может у кого-то есть идеи как можно решить задачу поиска MEX лучше?