Как наши любимые структуры данных и алгоритмы получили свои имена?
Некоторые алгоритмы, с которыми мы сталкиваемся, названы в честь их изобретателей, например, алгоритм кратчайшего пути Дейкстры назван в честь ученого-компьютерщика Эдсгера В. Дейкстры, который придумал алгоритм в 1956 году. Точно так же алгоритм Кнута-Морриса-Пратта (KMP) для поиска слова в другой текстовой строке назван в честь Джеймс Х. Моррис, Дональд Кнут и Вон Пратт.
Большинство структур данных и алгоритмов основаны на том, как они ведут себя или выглядят. Например, очереди и стеки названы из-за их поведения при отправке и извлечении. Деревья называются деревьями, потому что они похожи на перевернутые деревья. Точно так же существует множество алгоритмов, таких как сортировка вставками или сортировка слиянием, которые очень легко соотнести с их именами.
Но есть некоторые структуры данных и алгоритмы, которые не очень легко связать с их именами. Представляю некоторые из них:
Хеширование с кукушкой
Cuckoo Hashing — это алгоритм хеширования, который предлагает O(1) поиск в худшем случае. Это работает следующим образом:
Мы поддерживаем 2 хеш-таблицы и хеш-функцию, соответствующую каждой хеш-таблице. Итак, предположим, что хеш-таблицы — это H1 и H2. Хэш-функция для H1 — это f1, а хэш-функция для H2 — если f2. Теперь предположим, что нам нужно ввести значение x. Сначала мы проверяем, не пусто ли поле H1[f1(x)]. Если это так, мы помещаем x в эту позицию в H1.
Если она не пуста, мы освобождаем место для >x в H1, переместив элемент в это место, допустим y, в H2. Мы перемещаем значение y во второй хэш-таблице H2 в H2[f2(y)]. . Этот процесс продолжается и продолжается, т. е. если бы H2[f2(y)] не было бы пустым, мы бы переместили этот элемент, z, обратно на H1 в позиции H1[f1(z)].
Как появилась кукушка? Так получилось, что некоторые виды птенцов кукушки выталкивают другие яйца или детенышей из гнезда, когда они вылупляются, чтобы освободить место для себя! Отсюда и хеширование с кукушкой. Интересно, правда?
Красно-черное дерево — это своего рода самобалансирующееся бинарное дерево поиска.
Узлы в красно-черном дереве, как можно догадаться из самого названия, окрашены либо в красный, либо в черный цвет и используются для обеспечения того, чтобы дерево оставалось сбалансированным всякий раз, когда происходят вставки или удаления.
Меня всегда интересовало значение этих цветов. Ну, они могли использовать любые другие цвета, почему только черный и красный? Оказывается, это потому, что черный и красный были самыми красивыми цветами, которые производил цветной лазерный принтер, доступный авторам во время работы в Ксерокс Парк.
Пузырьковая сортировка или сортировка погружением
Хорошо, я знаю, что это легко! Пузырьковая сортировка — один из трех основных алгоритмов сортировки.
В пузырьковой сортировке мы сравниваем соседние элементы и меняем их местами, если левый больше правого.
Каждый раз, когда мы идем слева направо, выполняя эти перестановки, самый большой элемент в несортированном массиве опускается в конец. И в процессе мелкие элементы пузырятся. Отсюда и название «пузырьковая сортировка» или «тонущая сортировка».
Следите за новостями ;)
Источник:
https://en.wikipedia.org/wiki/