Решето Эратосфена за O(n). Доказательство

В комментариях к одному из прошлых постов о решете Эратосфена был упомянут
этот короткий алгоритм из Википедии:
Алгоритм 1:
1: для i := 2, 3, 4, …, до n:
2: если lp[i] = 0:
3: lp[i] := i
4: pr[] += {i}
5: для p из pr пока p ≤ lp[i]…

Обмен данными и дифференциальные уравнения

В одном из проектов, над которыми мне довелось работать, был реализован механизм обмена данными между удалёнными компонентами системы, работавший по следующему сценарию: компонент-источник А на своей стороне подготавливает данные, предназначенные для п…

Вейвлет — анализ.Часть 1

Введение
Рассмотрим дискретное вейвлет – преобразования (DWT), реализованное в библиотеке PyWavelets PyWavelets 1.0.3. PyWavelets — это бесплатное программное обеспечение с открытым исходным кодом, выпущенное по лицензии MIT.

При обработке данных н…

«Топологическая» сортировка графа с циклами

Полное название статьи должно было звучать как «Устойчивая „топологическая“ сортировка графа с циклами за O(|V| + |e| log |e|) по времени и O(|V|) по памяти без рекурсии», но мне сказали что это перебор. Читать дальше →…