Всем салют!
Хочу рассказать вам историю о том, как я начинал с уровня — «не могу решить даже 1 easy задачу из 10» до уровня — «могу решить каждую вторую medium задачу» и прошел несколько coding сессий в таких компаниях как Meta, Booking, Careem, Avito...
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я по прежнему буду крайне признательна за любые замечания в личку по улучшению качества перевода.
Опубликовано ранее:
Часть 1
Часть 2
Часть 3
Поздравляю! Теперь вы знаете о том, как анализировать сложность алгоритмов, что такое асимптотическая оценка и нотация «большое-О». Вы также в курсе, как интуитивно выяснить является ли сложностью алгоритма O( 1 ), O( log( n ) ), O( n ), O( n2 ) и так далее. Вы знакомы с символами o, O, ω, Ω, Θ и понятием «наихудшего случая». Если вы добрались до этого места, то моя статья уже выполнила свою задачу.
Этот финальный раздел — опциональный. Он несколько сложнее, так что можете не стесняясь пропустить его, если хотите.От вас потребуется сфокусироваться и потратить некоторое время на решение упражнений. Однако, так же здесь будет продемонстрирован очень полезный и мощный способ анализа сложности алгоритмов, что, безусловно, стоит внимания.
Читать полностью »
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я по прежнему буду крайне признательна за любые замечания в личку по улучшению качества перевода.
Опубликовано ранее:
Часть 1
Часть 2
.png "Введение в анализ сложности алгоритмов (часть 3)")
Если вы знаете, что такое логарифмы, то можете спокойно пропустить этот раздел. Глава предназначается тем, кто незнаком с данным понятием или пользуется им настолько редко, что уже забыл что там к чему. Логарифмы важны, поскольку они очень часто встречаются при анализе сложности. Логарифм — это операция, которая при применении её к числу делает его гораздо меньше (подобно взятию квадратного корня). Итак, первая вещь, которую вы должны запомнить: логарифм возвращает число, меньшее, чем оригинал. На рисунке справа зелёный график — линейная функция f(n) = n, красный — f(n) = sqrt(n), а наименее быстро возрастающий — f(n) = log(n). Далее: подобно тому, как взятие квадратного корня является операцией, обратной возведению в квадрат, логарифм — обратная операция возведению чего-либо в степень.
Читать полностью »
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я по прежнему буду крайне признательна за любые замечания в личку по улучшению качества перевода.
Опубликовано ранее:
Часть 1
Из предыдущей части можно сделать вывод, что если мы сможем отбросить все эти декоративные константы, то говорить об асимптотике функции подсчёта инструкций программы будет очень просто. Фактически, любая программа, не содержащая циклы, имеет f( n ) = 1, потому что в этом случае требуется константное число инструкций (конечно, при отсутствии рекурсии — см. далее). Одиночный цикл от 1 до n, даёт асимптотику f( n ) = n, поскольку до и после цикла выполняет неизменное число команд, а постоянное же количество инструкций внутри цикла выполняется n раз.
Читать полностью »
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы покажутся чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он будет полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я по прежнему буду крайне признательна за любые замечания в личку по улучшению качества перевода.
Многие нынешние программисты, пишущие классные и широко распространённые программы, имеют крайне смутное представление о теоретической информатике. Это не мешает им оставаться прекрасными творческими специалистами, и мы благодарны за то, что они создают.
Тем не менее, знание теории тоже имеет своё преимущества и может оказаться весьма полезным. В этой статье, предназначенной для программистов, которые являются хорошими практиками, но имеют слабое представление о теории, я представлю один из наиболее прагматичных программистских инструментов: нотацию «большое О» и анализ сложности алгоритмов. Как человек, который работал как в области академической науки, так и над созданием коммерческого ПО, я считаю эти инструменты по-настоящему полезными на практике. Надеюсь, что после прочтения этой статьи вы сможете применить их к собственному коду, чтобы сделать его ещё лучше. Также этот пост принесёт с собой понимание таких общих терминов, используемых теоретиками информатики, как «большое О», «асимптотическое поведение», «анализ наиболее неблагоприятного случая» и т.п.
Этот текст также ориентирован на учеников средней школы из Греции или любой другой страны, участвующих в Международной олимпиаде по информатике, соревнованиях по алгоритмам для учащихся и тому подобном. Как таковой, он не нуждается в знании каких-либо математических предпосылок и даст вам основу для дальнейшего исследования алгоритмов с твёрдым пониманием стоящей за ними теории. Как тот, кто в своё время много участвовал в различных состязаниях, я настоятельно рекомендую вам прочитать и понять весь вводный материал. Эти знания будут просто необходимы, когда вы продолжите изучать алгоритмы и различные передовые технологии.
Я надеюсь, что это текст будет полезен для тех программистов-практиков, у которых нет большого опыта в теоретической информатике (то, что самые вдохновлённые инженеры-программисты никогда не ходили в колледж, уже давно свершившийся факт). Но поскольку статья предназначена и для студентов тоже, то временами она будет звучать, как учебник. Более того, некоторые темы могут показаться вам чересчур простыми (например, вы могли сталкиваться с ними во время своего обучения). Так что, если вы чувствуете, что понимаете их — просто пропускайте эти моменты. Другие секции идут несколько глубже и являются более теоретическими, потому что студенты, участвующие в соревнованиях, должны разбираться в теории алгоритмов лучше, чем средний практик. Но знать эти вещи не менее полезно, а следить за ходом повествования не так уж сложно, так что они, скорее всего, заслуживают вашего внимания. Оригинальный текст был направлен учащимся старшей школы, никаких особых математических знаний он не требует, поэтому каждый, имеющий опыт программирования (например, знающий, что такое рекурсия) способен понять его без особых проблем.
В этой статье вы найдёте много интересных ссылок на материалы, выходящие за рамки нашего обсуждения. Если вы — работающий программист, то вполне возможно, что знакомы с большинством из этих концепций. Если же вы просто студент-новичок, участвующий в соревнованиях, переход по этим ссылкам даст вам информацию о других областях информатики и разработки программного обеспечения, которые вы ещё не успели изучить. Просмотрите их ради увеличения собственного багажа знаний.
Нотация «большого О» и анализ сложности алгоритмов — это те вещи, которые и программисты-практики, и студенты-новички часто считают трудными для понимания, боятся или вообще избегают, как бесполезные. Но они не так уж сложны и заумны, как может показаться на первый взгляд. Сложность алгоритма — это всего лишь способ формально измерить, насколько быстро программа или алгоритм работают, что является весьма прагматичной целью. Давайте начнём с небольшой мотивации по этой теме.
Читать полностью »
