Информатика

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

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

5 формул

Формулы темы

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

Индекс Жаккара показывает долю общих элементов в объединении двух множеств. Он принимает значения от 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$

Закон Амдала: предел ускорения параллельной программы

Закон Амдала оценивает ускорение неизменной задачи на N одинаковых исполнителях, если долю p исходного времени можно идеально распараллелить. Последовательная часть ограничивает итоговый выигрыш.

$S(N)=\frac{1}{(1-p)+p/N}$