Архив метки: algorithm

Рандом с учетом весов за O(1) — Walker’s alias method

Есть массив A[n] с весами. Нужно выбрать случайный элемент, но не равномерным рандомом, а в соответствии с этими весами. (В общем, это дискретное распределение вероятности) Чем примечателен метод алиаса, так это константным временем выполнения O(1)

Рубрика: Алгоритмы, Программирование, Разное | Метки: , , , | 2 комментария

Расстояние Левенштейна — определяем «похожесть» строк

Интересный и очень полезный алгоритм «дистанция Левенштейна» (Levenshtein distance), так же известная как редакционное расстояние или дистанция редактирования. Эта «дистанция» — это минимальное количество правок одной строки (под правками подразумеваются три возможные операции: стирание символа, замена символа и вставка символа), чтобы … Читать далее

Рубрика: Алгоритмы | Метки: , , | 18 комментариев