точность вычислений

Статьи

SRT Алгоритм Троичный поиск Вершина унимодальной функции: сравнить две точки и отбросить часть отрезка. И почему золотое сечение лучше. O(log(L/ε)) вычислений функции 2 задачи GRA Алгоритм Алгоритм Беллмана — Форда Кратчайшие пути с отрицательными рёбрами и поиск отрицательного цикла: V раундов по всем рёбрам. O(V · E) 2 задачи NUM Алгоритм Длинная арифметика Числа длиннее машинного слова: цифры по основанию 10⁹ или 2³⁰, переносы, столбик и дорогая печать.

сложение O(n), умножение и деление столбиком O(n²), печать в десятичной записи O(n²) или O(M(n) log n)

2 задачи NUM Алгоритм Быстрое преобразование Фурье Дискретное преобразование Фурье за O(N log N): спектры, свёртки, умножение многочленов и больших чисел. O(N log N) 2 задачи NUM Алгоритм Теоретико-числовое преобразование БПФ без округлений: корень из единицы — 17 по модулю 3329, и так ваш браузер умножает многочлены постквантового ключа. O(n log n) 1 задача NUM Алгоритм Метод Гаусса Линейная система исключением: ведущий элемент, LU, обусловленность, разреженные матрицы и заполнение. O(n³): около n³/3 умножений на прямой ход 2 задачи GEO Приём Векторы и ориентация Знак векторного произведения — поворот налево или направо; на нём стоит почти вся вычислительная геометрия. O(1) на один поворот 2 задачи GEO Алгоритм Пересечение отрезков Где встречаются два отрезка — точно, в дробях; и как найти все встречи среди тысяч отрезков без перебора пар. O(1) на пару; O(n²) перебором для n отрезков 2 задачи GEO Алгоритм Площадь многоугольника Площадь по координатам вершин: сумма xᵢyᵢ₊₁ − xᵢ₊₁yᵢ, а её знак — направление обхода. O(n) 2 задачи NUM~ Алгоритм Бисекция и метод Ньютона Корень уравнения: деление отрезка пополам надёжно, касательные Ньютона — быстро. бисекция — log₂((b − a)/ε) шагов; Ньютон — около log₂ от числа знаков 2 задачи NUM~ Алгоритм Численное интегрирование Площадь под кривой суммой: трапеции, Симпсон, узлы Гаусса, адаптивный шаг и оценка ошибки по Рунге. O(n) вычислений функции 2 задачи NUM~ Алгоритм Методы Эйлера и Рунге — Кутты Шаг за шагом по закону движения: Эйлер, РК4, адаптивный шаг, Верле для орбит и неявные схемы. O(T/h) шагов, у РК4 четыре вычисления правой части на шаг 2 задачи NUM~ Приём Суммирование Кэхэна Сложить миллионы дробных чисел и не растерять младшие разряды: поправка Кэхэна, попарное и точное суммирование. O(n) 1 задача NUM~ Алгоритм Симплекс-метод 24 числа вместо 88 клавиш — и симплекс-метод восстанавливает каждый аккорд прелюдии Шопена точно. Наименьшие квадраты — ни одного.

шаг — O(m·n); число шагов на практике порядка m, в худшем случае экспоненциальное

1 задача ML Алгоритм Наивный Байес Считает, как часто каждый признак встречается в каждом классе, и складывает логарифмы этих частот. O(N) обучение, O(L·m) ответ 2 задачи ML Алгоритм Логистическая регрессия Оценивает вероятность ответа «да»: взвешенная сумма признаков, пропущенная через сигмоиду. O(n·d² + d³) на шаг Ньютона 3 задачи TEC Приём Векторизация Вынести цикл из интерпретатора в операции над целыми массивами: что ускоряется в сотни раз и что не векторизуется. та же O(n), что у цикла 2 задачи

Задачи

Вердикт по замерам Выборка по энергии Где будет тело через время T Где встречаются отрезки Градусо-часы по датчику с пропусками Маршруты без шагов назад Определитель языка Переполнится ли буфер Площадь района из нескольких кусков Самый дальний бросок Сколько стоит рассрочка Сопротивление цепи Судья прогнозов Упростить тропу Цепочки переносов Честный интервал для озера Этажи индекса Весь отрыв в кадре Время круга Выгодный круг обменов Давление в центре планеты Есть ли лучшая кривая Индекс из прямых Навигатор без тригонометрии Наивные веса Неявный шаг сквозь стену Сколько раз перепишется резервуар Точная сумма Уравнение Кеплера без осечек Хвост суммы кубиков

Часто рядом

классика 13 в проде 7 собеседования 6 итерации 5 наука и физика 5 олимпиады 5 разделяй и властвуй 4 оптимизация 3 массив 3 точки на плоскости 3 карты и навигация 3 геоданные 3