Почему важно изучать алгоритмы
Алгоритмы важны, потому что это суть программ?
Для меня «суть» программ всё же в том, чтобы приносить пользу людям и улучшать их жизнь. Мне больше нравится другая метафора: игра в шахматы.
Человек, изучивший, как ходят фигуры, может играть, даже составлять некоторые планы, как прийти к победе, и в конечном счёте выигрывать. Но понятно, что если такой человек начнёт игру против опытного гроссмейстера — это, скорее всего, окончится проигрышем. Гроссмейстер держит в уме что-то ещё кроме правил хода фигур — общую ситуацию на доске, сильные и слабые позиции, оценки рисков при тех или иных вариантах своих атак — и использует всю эту информацию, чтобы выбрать наилучший ход.
Точно так же и человек, который освоил синтаксис языка программирования, вероятно, уже сможет решать задачи с его помощью. Но часто эти решения, увы, не могут за разумное время справиться с объёмами данных, с которыми приходится иметь дело ИТ-компаниям. Или автор не учёл какой-нибудь редкий случай, при котором программа вдруг начинает работать неправильно. Случается и такое, что программа корректно решает поставленную задачу, но на это уходит непропорционально много времени и сил.
Представление об алгоритмах, их сложности, сильных и слабых сторонах позволяет преодолеть эти проблемы. Если знание языка программирования — это понимание, как ходят шахматные фигуры, то знание алгоритмов — умение играть так, чтобы выигрывать.
Понятно! А правда ли нельзя стать хорошим разработчиком, не разбираясь в алгоритмах? Или можно?
Разработка — занятие многогранное, и вряд ли стоит категорично утверждать, что «без алгоритмов совсем ничего разрабатывать нельзя» или «любой уважающий себя разработчик должен знать следующий список алгоритмов: <вписать нужное>».
Знание алгоритмов нужно разработчику, чтобы не просаживать производительность на ровном месте, не совершать ошибок там, где их быть не должно. Грубо говоря, не рубить дрова тупой стороной топора. Понятно, что при должном усердии получить наломанные куски дерева можно и таким способом, но если применить топор правильно, то всем будет лучше.
Слышал такое мнение, что фрагменты, имеющие сложность O(N²), требуют много труда при отладке и модификации программ. Их сравнительно легко придумать и запрограммировать, на небольших объёмах данных (а тестовые часто оказываются именно такими) они работают быстро. Но когда данных становится много, именно эти фрагменты оказываются виновниками замедления программы.
Представим, что кто-то создал сайт, где можно голосовать за любимые музыкальные группы. На сайте показывается список групп, упорядоченный по убыванию числа голосов. При этом автор решил использовать сортировку пузырьком — тот самый фрагмент, имеющий сложность O(N²), — потому что хорошо умел её писать. Пока групп были сотни, сортировка работала за доли секунды и никто не замечал подвоха. Но когда количество групп достигло миллиона, для сортировки списка требовались уже часы. Если бы автор использовал более производительный алгоритм сортировки, он всё так же заканчивал бы работу за доли секунды.
Знание алгоритмов страхует программиста от добавления подобных «бомб замедленного действия» в свой код. Но, конечно, далеко не во всех областях разработки нужно постоянно использовать наиболее эффективное решение.
Откуда тогда у работодателей такой упор на проверку знания алгоритмов? И на олимпиадах по программированию — тоже...
Насколько мне известно, когда в 1989 году планировали первую международную олимпиаду по информатике, организаторы задумались: как формулировать задания, чтобы их понимали участники из разных стран, которые по-разному изучали связанные с информатикой темы? Ответ оказался простым, но важным: роль международного языка, который одинаково хорошо понимали связанные с информатикой люди из разных стран, взяли на себя языки программирования. Так появились те самые задачи на составление программ, которые до сих пор доминируют на олимпиадах по информатике всех возможных уровней.
Логично, что более высоко следует оценить программу, которая работает не только корректно, но и эффективно. Поэтому в олимпиадных задачах мы практически всегда встречаем ограничения на время работы программы и объём используемой оперативной памяти. Как правило, очевидные решения не могут обработать требуемый объём данных и уложиться в эти лимиты, так что участникам нужно продемонстрировать умение грамотно применять структуры данных и методы решения, чтобы составить по-настоящему эффективную программу.
Что касается популярности алгоритмических задач при собеседовании на работу — я считаю, причины во многом похожи. Представьте, что вы руководитель крупной группы разработки, которому нужно найти нового сотрудника. Соискателей у вас много — настолько, что лично встретиться и поговорить с каждым из них не получится. Опыт у людей непохожий: они работали над разными проектами, по-разному изучали программирование, в их компаниях наверняка использовались разные соглашения о том, как писать программы.
Как же вам выбрать хотя бы группу людей, с которыми перспективно далее встретиться лично? Получается, нужно провести среди соискателей небольшую «олимпиаду». Несмотря на разный опыт, все ваши кандидаты наверняка «говорят на одном языке» — языке составления программ. Поэтому на собеседованиях так часто дают задачи, в которых требуется написать небольшую, но нетривиальную программу. Это позволяет не только выяснить, умеет ли кандидат вообще программировать, но и понять, как он мыслит, как конкретизирует неоднозначные детали в задании, насколько адекватное решение он может составить, насколько успешно он может его запрограммировать, учитывает ли он возможные трудные случаи, как проверяет корректность своего решения и, наконец, как он не сдаётся в стрессовой ситуации.
В реальной работе от сотрудника вряд ли потребуется за час с нуля придумывать алгоритмические решения. С другой стороны, всё описанное выше — это тот же жизненный цикл большинства программных продуктов или сервисов, только пройденный в миниатюре, на примере небольшой задачи. Кандидат, который успешно справляется с такими задачами на стартовых этапах собеседования, определённо молодец.
Можно ли сделать знание алгоритмов своим ключевым преимуществом в учёбе или работе? Стать этаким гуру алгоритмов...
Сразу представляется ситуация: разработка большого и важного проекта столкнулась с непреодолимой проблемой. Руководитель звонит специальному человеку, у которого в должности написано «Консультант по алгоритмам». Через некоторое время такси привозит в офис таинственного персонажа, который запирается в комнате для встреч с ключевыми руководителями проекта, беседует с ними — и находит блестящее решение, как гениальный детектив.
Звучит интригующе, но не думаю, что подобное встречается в жизни. Кажется, очень немногие люди могли бы похвастаться тем, что их основная работа — именно придумывать новые, неизвестные человечеству ранее алгоритмы. Как правило, разработчик определённого проекта со временем наращивает экспертизу в алгоритмах, нужных для его работы. Например, разработчик систем для текстового поиска наверняка знаком с алгоритмами обработки строк, тогда как разработчик маршрутизации такси лучше знает графовые алгоритмы.
С другой стороны, упор на алгоритмы во время обучения — неплохая инвестиция. Школьник или студент с хорошей алгоритмической подготовкой может участвовать в соревнованиях, которые помогают оценить и сравнить свой текущий уровень с другими. И конечно, изучая алгоритмы и решая задачи, проще попасть в университет или на стажировку в компанию мечты. Упорство в изучении алгоритмов может обернуться социальным лифтом и оказать большое влияние на дальнейшую жизнь.
Пошли учиться! Как вообще вникать в эту тему, с чего начинать?
Сейчас по программированию и алгоритмам есть множество онлайн-курсов, в том числе полностью бесплатных. Несколько хороших русскоязычных курсов можно найти на платформе Stepik. Есть также сайты с теоретической информацией в текстовом виде: легендарный e-maxx, neerc.ifmo, Algocode wiki, notes.algoprog, acm.khpnets.info.
Если говорить о книгах, то часто упоминают классический учебник «Алгоритмы. Построение и анализ» Томаса Кормена и соавторов. Это действительно важная книга, но она объёмная и рассчитана скорее на читателя, уже имеющего определённую подготовку. Я, признаться, не знаком ни с одним человеком, который прочёл бы её целиком, от корки до корки. Зато с этой книгой прекрасно работать как со справочником, читая отдельные главы по мере знакомства с соответствующими темами.
Из классических учебников мне очень понравилась книга Algorithms Роберта Седжвика и Кевина Уэйна. Она переведена как «Алгоритмы на Java», но я бы советовал найти её в исходном варианте. У авторов этой книги есть потрясающий одноимённый бесплатный курс на платформе Coursera — правда, англоязычный.
Наиболее тонкая из «серьёзных» книг — кажется, «Алгоритмы» Санджоя Дасгупты и соавторов. В качестве обзорной книги для знакомства с предметом я бы выбрал «Алгоритмы. Вводный курс» Томаса Кормена. Я знаю, что многим нравится книга Адитьи Бхаргавы «Грокаем алгоритмы», но на меня она произвела неоднозначное впечатление.
Понятно, что теоретические знания крайне желательно закреплять практикой. Для русскоязычных новичков наиболее полезны архивы Красноярского краевого дворца пионеров и Московского центра непрерывного математического образования. На этих сайтах есть тысячи задач, от совсем несложных и до олимпиад всероссийского уровня. Решать их можно прямо на сайте, отправляя текст программы и сразу получая вердикт.
Если вы выбрали путь покорения олимпиад, то рано или поздно познакомитесь с Codeforces — крупнейшей платформой для проведения соревнований по программированию. Там регулярно проводятся онлайн-раунды, а уровень задач существенно серьёзнее, чем на других ресурсах. У вас есть возможность посоревноваться с лучшими олимпиадными программистами мира.
Если хотите порешать задачи для подготовки к собеседованию, подойдёт LeetCode. Здесь тоже проводятся еженедельные соревнования, но сами задания компактнее, чем аналоги из других архивов. Также тренировки по алгоритмам запускает команда Y&&Y, а в Яндекс Практикум есть курс «Алгоритмы и структуры данных».
Что делать, если алгоритмизация вообще не даётся?
Если вы уже умеете программировать, но у вас почему-то стабильно не получается решать алгоритмические задачи, возможно, вы начали со слишком сложных. Если вы пользуетесь онлайн-архивом, отсортируйте список задач по убыванию количества принятых решений и начните с простых. Иногда имеет смысл на первых порах поменять сам архив: например, я знаю совсем мало людей, которые с нуля начали успешно решать Codeforces.
Если вы изучаете алгоритмы самостоятельно, полезно пройти какой-либо полновесный онлайн-курс, чтобы связать кусочки информации в памяти в единую картину. Желательно, чтобы у курса были также практические задания: без практики даже очень хорошо объяснённая теория забывается.
Найдите друзей, с которыми вы будете вместе учиться и, может быть, даже соперничать. Очень часто это помогает сильнее, чем кажется на первый взгляд.
И даже если ничего не получается, не стоит опускать руки. Computer Science — это бесконечно разнообразная область, и она не сводится к чему-то одному, в том числе к знанию алгоритмов. Наверняка у вас есть талант, который ждёт своего применения.
