Информатика: темы
Алгоритмы и анализ данных
Сравнение множеств, векторов и строк, поиск и оценка числа операций.
5 формул
Таблица формул
| Формула | Запись | Тема | Для чего нужна |
|---|---|---|---|
| Индекс Жаккара: сходство через пересечение множеств | $J(A,B)=\frac{|A\cap B|}{|A\cup B|}$ | Алгоритмы и анализ данных | Индекс Жаккара показывает долю общих элементов в объединении двух множеств. Он принимает значения от 0 до 1: ноль означает отсутствие пересечения, а единица — совпадение множеств. |
| Косинусное сходство векторов: формула и расчёт угла | $\cos\theta=\frac{a\cdot b}{\lVert a\rVert\,\lVert b\rVert}$ | Алгоритмы и анализ данных | Косинусное сходство сравнивает направление двух ненулевых векторов и принимает значения от −1 до 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]\}$ | Алгоритмы и анализ данных | Расстояние Левенштейна — минимальное число вставок, удалений и замен стоимостью 1, превращающих одну строку в другую. Перестановка соседних символов отдельной операцией не считается. |
| Неравенство Крафта: длины двоичных префиксных кодов | $\sum_{i=1}^{m}2^{-l_i}\le 1$ | Кодирование информации | Неравенство Крафта проверяет, могут ли заданные длины двоичных слов образовать префиксный код: сумма 2 в степени минус длина не должна превышать единицу. |
| Двоичный поиск: максимальное число сравнений ключа | $C_{\max}(n)=\lfloor\log_2 n\rfloor+1,\quad n\ge1$ | Алгоритмы и анализ данных | Двоичный поиск в отсортированном массиве отбрасывает половину диапазона после каждого трехстороннего сравнения. В худшем случае для n≥1 требуется не более ⌊log₂ n⌋+1 итераций. |