Информатика

Алгоритмы и анализ данных

Сравнение множеств, векторов и строк, поиск и оценка числа операций.

4 формулы

Формулы темы

Индекс Жаккара: сходство через пересечение множеств

Индекс Жаккара показывает долю общих элементов в объединении двух множеств. Он принимает значения от 0 до 1: ноль означает отсутствие пересечения, а единица — совпадение множеств.

$J(A,B)=\frac{|A\cap B|}{|A\cup B|}$

Косинусное сходство векторов: формула и расчёт угла

Косинусное сходство сравнивает направление двух ненулевых векторов и принимает значения от −1 до 1. Для неотрицательных векторов оно показывает, насколько совпадает профиль признаков.

$\cos\theta=\frac{a\cdot b}{\lVert a\rVert\,\lVert b\rVert}$

Расстояние Левенштейна: вставки, удаления и замены

Расстояние Левенштейна — минимальное число вставок, удалений и замен стоимостью 1, превращающих одну строку в другую. Перестановка соседних символов отдельной операцией не считается.

$D(i,j)=\min\{D(i-1,j)+1,D(i,j-1)+1,D(i-1,j-1)+[a_i\ne b_j]\}$

Двоичный поиск: максимальное число сравнений ключа

Двоичный поиск в отсортированном массиве отбрасывает половину диапазона после каждого трехстороннего сравнения. В худшем случае для n≥1 требуется не более ⌊log₂ n⌋+1 итераций.

$C_{\max}(n)=\lfloor\log_2 n\rfloor+1,\quad n\ge1$