оценка

Статьи

SRT Приём Нижние границы сравнений Почему нельзя быстрее: подсчёт исходов и игра против судьи; сортировка, второй в турнире, минимум с максимумом, слияние. сортировка — ⌈log₂ n!⌉ сравнений 1 задача GRA Приём Как хранить граф Матрица, списки, массив рёбер и CSR: память, скорость и какие вопросы каждая запись задаёт дёшево.

соседи вершины: O(n) у матрицы, O(deg) у списков и CSR; есть ли ребро: O(1) у матрицы, O(deg) у списков

2 задачи DP Алгоритм Выравнивание последовательностей Лучшее сопоставление двух последовательностей с очками за замены и пропуски: целиком, по кускам и с проверкой на случайность. O(m · n) 2 задачи NUM~ Алгоритм Метод Монте-Карло Оценка числа случайным опытом: ошибка 1/√n в любой размерности, честный доверительный интервал. O(n) испытаний, ошибка ~ σ/√n 2 задачи RND Приём Лас-Вегас и Монте-Карло Всегда верный, но иногда долгий против всегда быстрого, но иногда неверного — и как превратить одно в другое. O(k · стоимость одной попытки) 2 задачи RND Приём Случайные блуждания Шаг наугад на каждом перекрёстке: √t, время до цели, «кто первый» и 2-SAT случайным блужданием. O(1) на шаг 2 задачи TEC Приём O-большое Как растёт работа вместе с данными: O, Ω и Θ, правила оценки кода и где асимптотика обманывает. оценка — по тексту программы 1 задача TEC Приём Как честно измерить скорость Повторы, прогрев, медиана и минимум, timeit и testing.Benchmark — и типичные способы обмануть себя замером. повторов столько, чтобы замер шёл хотя бы десятую долю секунды 1 задача TEC Приём Сколько операций в секунду Шаги алгоритма, делённые на скорость языка, — и вы знаете, уложится ли программа, ещё до того, как её написали. оценка — секунды в уме 1 задача TEC Приём Сложность по замерам Рост времени по замерам: наклон, проверка отношением, экспоненты — и где замер врёт. O(B) на попытку 1 задача TEC Приём Числа, которые стоит знать Кэш, память, диск и сеть отличаются в сотни раз — прикидка по этим числам показывает, что ускорять. прикидка — минута на салфетке 1 задача TEC Приём Сколько займёт в памяти Байты на запись — и сразу видно, поместится ли миллиард: из чего складывается вес данных в Python и Go. прикидка — байты на запись × число записей 1 задача

Задачи

Есть ли такой участок Рассчитать фильтр Вердикт по замерам Во сколько раз длиннее по улицам Корень k-й степени Переполнится ли буфер Проверка за сервером Сколько останется схем Судья прогнозов Толчки рядом во времени Честный интервал для озера Водопад загрузки Когда начинать заново Промахи кэша Размер блока Сколько раз выполнится строка Сколько раз перепишется резервуар Топ по частям Хвост суммы кубиков Блуждание по папкам

Часто рядом

собеседования 8 классика 7 замеры 6 матрица 3 случайность 3 в проде 3 сортировка 2 граф 2 массив 2 хеш-таблица 2 дружит с кэшем 2 карты и навигация 2