Pull to refresh
5
0
Анна Муравьева @Anna-Mur

ML engineer, аналитик данных

Send message

Введение в анализ сложности алгоритмов (часть 4)

Reading time5 min
Views100K
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.


Опубликовано ранее:
Часть 1
Часть 2
Часть 3

Оптимальная сортировка


Поздравляю! Теперь вы знаете о том, как анализировать сложность алгоритмов, что такое асимптотическая оценка и нотация «большое-О». Вы также в курсе, как интуитивно выяснить является ли сложностью алгоритма O( 1 ), O( log( n ) ), O( n ), O( n2 ) и так далее. Вы знакомы с символами o, O, ω, Ω, Θ и понятием «наихудшего случая». Если вы добрались до этого места, то моя статья уже выполнила свою задачу.

Этот финальный раздел — опциональный. Он несколько сложнее, так что можете не стесняясь пропустить его, если хотите.От вас потребуется сфокусироваться и потратить некоторое время на решение упражнений. Однако, так же здесь будет продемонстрирован очень полезный и мощный способ анализа сложности алгоритмов, что, безусловно, стоит внимания.
Читать дальше →
Total votes 58: ↑54 and ↓4+50
Comments6

Введение в анализ сложности алгоритмов (часть 3)

Reading time6 min
Views127K
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.


Опубликовано ранее:
Часть 1
Часть 2

Логарифмы


image
Если вы знаете, что такое логарифмы, то можете спокойно пропустить этот раздел. Глава предназначается тем, кто незнаком с данным понятием или пользуется им настолько редко, что уже забыл что там к чему. Логарифмы важны, поскольку они очень часто встречаются при анализе сложности. Логарифм — это операция, которая при применении её к числу делает его гораздо меньше (подобно взятию квадратного корня). Итак, первая вещь, которую вы должны запомнить: логарифм возвращает число, меньшее, чем оригинал. На рисунке справа зелёный график — линейная функция f(n) = n, красный — f(n) = sqrt(n), а наименее быстро возрастающий — f(n) = log(n). Далее: подобно тому, как взятие квадратного корня является операцией, обратной возведению в квадрат, логарифм — обратная операция возведению чего-либо в степень.
Читать дальше →
Total votes 74: ↑60 and ↓14+46
Comments4

Введение в анализ сложности алгоритмов (часть 2)

Reading time11 min
Views172K
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы могут показаться читателю чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он окажется полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.


Опубликовано ранее:
Часть 1

Сложность


Из предыдущей части можно сделать вывод, что если мы сможем отбросить все эти декоративные константы, то говорить об асимптотике функции подсчёта инструкций программы будет очень просто. Фактически, любая программа, не содержащая циклы, имеет f( n ) = 1, потому что в этом случае требуется константное число инструкций (конечно, при отсутствии рекурсии — см. далее). Одиночный цикл от 1 до n, даёт асимптотику f( n ) = n, поскольку до и после цикла выполняет неизменное число команд, а постоянное же количество инструкций внутри цикла выполняется n раз.
Читать дальше →
Total votes 55: ↑53 and ↓2+51
Comments16

Введение в анализ сложности алгоритмов (часть 1)

Reading time10 min
Views386K
От переводчика: данный текст даётся с незначительными сокращениями по причине местами излишней «разжёванности» материала. Автор абсолютно справедливо предупреждает, что отдельные темы покажутся чересчур простыми или общеизвестными. Тем не менее, лично мне этот текст помог упорядочить имеющиеся знания по анализу сложности алгоритмов. Надеюсь, что он будет полезен и кому-то ещё.
Из-за большого объёма оригинальной статьи я разбила её на части, которых в общей сложности будет четыре.
Я (как всегда) буду крайне признательна за любые замечания в личку по улучшению качества перевода.


Введение


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

Тем не менее, знание теории тоже имеет свои преимущества и может оказаться весьма полезным. В этой статье, предназначенной для программистов, которые являются хорошими практиками, но имеют слабое представление о теории, я представлю один из наиболее прагматичных программистских инструментов: нотацию «большое О» и анализ сложности алгоритмов. Как человек, который работал как в области академической науки, так и над созданием коммерческого ПО, я считаю эти инструменты по-настоящему полезными на практике. Надеюсь, что после прочтения этой статьи вы сможете применить их к собственному коду, чтобы сделать его ещё лучше. Также этот пост принесёт с собой понимание таких общих терминов, используемых теоретиками информатики, как «большое О», «асимптотическое поведение», «анализ наиболее неблагоприятного случая» и т.п.
Читать дальше →
Total votes 106: ↑98 and ↓8+90
Comments27

Как подготовить и провести A/B-тестирование. Базовый роадмэп для новичков

Reading time12 min
Views24K

Хабр, привет! 

Меня зовут Полина Окунева, я работаю ведущим аналитиком в компании GlowByte в команде Advanced Analytics, а также автор курса по A/B тестам. Сегодня в статье я предлагаю интересующимся небольшой гайд по A/B-тестам.

Когда я начала погружаться в тему A/B-тестирования пару лет назад, меня кидало из стороны в сторону: то перечитывала фундаментальные учебники по статистике, то переключалась на статьи о конкретных методиках. Но во всем этом многообразии материалов для меня на тот момент был огромный недостаток — я не могла собрать все в кучу и разобраться, а как же проводить-то этот A/B-тест? Я знала, что есть разные виды тестов, множественное тестирование и поправки, полезный и популярный Bootstrap… Но как все это соединить было не очевидно. Хотелось понять, какие этапы есть у A/B-тестирования и когда на что обращать внимание. Хотя бы какие термины гуглить и когда.

Сегодня я представляю вашему вниманию пазл, который сложился в моей голове по итогу плотной работы в этой теме. Я не претендую на истину в последней инстанции — шаги могут и должны(!) быть адаптированы конкретно под вашу задачу. Но если вы только начинаете входить в сферу A/B-тестирования, надеюсь, статья будет очень полезна. Я не буду подробно останавливаться на каждом понятии. Моя цель — обозначить технические этапы и показать новичкам модельную картину A/B-тестирования.

Читать далее
Total votes 13: ↑13 and ↓0+13
Comments0

Полное практическое руководство по Docker: с нуля до кластера на AWS

Reading time39 min
Views1.7M



Содержание



Вопросы и ответы


Что такое Докер?


Определение Докера в Википедии звучит так:


программное обеспечение для автоматизации развёртывания и управления приложениями в среде виртуализации на уровне операционной системы; позволяет «упаковать» приложение со всем его окружением и зависимостями в контейнер, а также предоставляет среду по управлению контейнерами.



Ого! Как много информации.

Читать дальше →
Total votes 125: ↑124 and ↓1+123
Comments44

Как не перестать быть data driven из-за data driften, или Пару слов о дрейфе данных

Reading time20 min
Views7.8K

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

В статье мы – команда Advanced Analytics GlowByte – поговорим о типах и причинах дрейфа, а также разберём на примере основные методы детекции дрейфа.

Читать далее
Total votes 10: ↑10 and ↓0+10
Comments0

Information

Rating
Does not participate
Works in
Registered
Activity

Specialization

Data Analyst, Data Scientist