Рубрика «сложность алгоритма»

В комментариях к одному из прошлых постов о решете Эратосфена был упомянут этот короткий алгоритм из Википедии:

Алгоритм 1:

1: для i := 2, 3, 4, ..., до n: 
2:  если lp[i] = 0:
3:       lp[i] := i
4:       pr[] += {i}
5:   для p из pr пока p ≤ lp[i] и p*i ≤ n:
6:       lp[p*i] := p
Результат:
 lp - минимальный простой делитель для кажого числа до n
 pr - список всех простых до n.

Алгоритм простой, но не всем он показался очевидным. Главная же проблема в том, что на Википедии нет доказательства, а ссылка на первоисточник (pdf) содержит довольно сильно отличающийся от приведенного выше алгоритм.

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

Примечание. Сокращенный перевод, скорее пересказ своими словами.
UPD: как отметили в комментариях, примеры не идеальны. Автор не ищет лучшее решение задачи, его цель объяснить сложность алгоритмов «на пальцах».

Big O нотация нужна для описания сложности алгоритмов. Для этого используется понятие времени. Тема для многих пугающая, программисты избегающие разговоров о «времени порядка N» обычное дело.

Если вы способны оценить код в терминах Big O, скорее всего вас считают «умным парнем». И скорее всего вы пройдете ваше следующее собеседование. Вас не остановит вопрос можно ли уменьшить сложность какого-нибудь куска кода до n log n против n^2.

Структуры данных

Выбор структуры данных зависит от конкретной задачи: от вида данных и алгоритма их обработки. Разнообразные структуры данных (в .NET или Java или Elixir) создавались под определенные типы алгоритмов.

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

Здесь мы будем использовать только массивы чисел (прямо как на собеседовании). Примеры на JavaScript.
Читать полностью »

Так сложилось, что последние полгода я активно занимался тестами производительности и мне кажется, что в этой области IT царит абсолютное непонимание происходящего. В наше время, когда рост вычислительных мощностей снизился (vertical scalability), а объем задач растет с прежней скоростью, проблема производительности становится всё острее. Но прежде, чем броситься на борьбу с производительностью, необходимо получить количественную характеристику.

Краткое содержание статьи:

Предыстория

Однажды, путешествуя в поезде, я захотел посчитать, каково расстояние между столбами электропередач. Вооружившись обычными часами и оценивая среднюю скорость поезда 80-100км/ч (25 м/с), я засекал время между 2-мя столбами. Как ни странно, этот наивный метод давал очень удручающие результат, вплоть до 1.5-2 кратной разницы. Естественно метод несложно было исправить, что я и сделал, достаточно было засечь 1 минуту и посчитать количество столбов. И не важно, что мгновенная скорость на протяжении минуты может варьироваться и даже не важно посчитаем мы последний столб или минута истечет посередине, потому как измерений вполне достаточно для требуемого результата.
Смысл теста в том, чтобы получить убедительные для себя и для других измерения.

Тесты «на коленке»

Эта история мне напоминает то, что происходит с тестированием производительности в Software Engineering. Достаточно частое явление — запуск 1-2 тестов, построение графиков и получение выводов о scalability система. Даже, если есть возможность применить МНК или узнать стандартную ошибку, это не делается за «ненадобностью.» Особенно интересная ситуация, когда после этих 2 измерений, люди обсуждают насколько быстрая система, как она масштабируется и сравнивают её с другими системами по личным ощущениям.
Конечно, оценить, насколько быстро выполняется команда, не сложно. С другой стороны, быстрее не значит лучше. Системы ПО имеют свыше 10 различных параметров, от hardware на котором они работают до input, которые вводит пользователь в разные моменты времени. И зачастую 2 эквивалентных алгоритма могут давать совершенно разные параметры масштабируемости в разных условиях, что делает выбор совсем не очевидным.

Недоверие к тестам

С другой стороны результаты измерений всегда остаются источником спекуляций и недоверий.
— Вчера мы меряли было X, а сегодня 1.1*X. Кто-то что-то менял? — 10% — это нормально, у нас теперь больше записей в БД.
— При проведении теста был отключен антивирус, скайп, анимация заставки?
— Не-не, для нормальных тестов нам надо закупить кластер серверов, установить микросекундную синхронизацию времени между ними… удалить ОС, запускать в защищенном режиме…
— Сколько пользователей мы поддерживаем? У нас 5000 зарегистрированных пользователей, вдруг 20% из них залогинится, надо запускать тесты с 1000 параллельными агентами.

Читать полностью »


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js