1. Бинарный поиск
Бинарный поиск – это одна из первых вещей, с которыми сталкиваются в начале изучения computer science. Это возможно самый простой пример того, как немного изобретательности может сделать решения, в буквальном смысле, экспоненциально более эффективными.
Его суть в том, что нам дан отсортированный массив. Необходимо итеративно делить его пополам, брать значение в середине и сравнивать его с элементом, который хотим найти: если он больше – ищем в правой половине, если меньше – в левой. И так до тех пор, пока элемент не будет найден.
Алгоритм бинарного поиска заключается в поиске элемента в упорядоченном массиве. Он работает следующим образом:
1. Задаем границы поиска: начало и конец массива.
2. Находим середину массива (индекс = (начало + конец) / 2).
3. Если искомый элемент равен элементу в середине массива, то поиск завершен.
4. Если искомый элемент меньше элемента в середине массива, то делаем новую границу концом массива слева от середины.
5. Если искомый элемент больше элемента в середине массива, то делаем новую границу началом массива справа от середины.
6. Повторяем шаги 2-5, пока не будет найден искомый элемент или пока границы поиска не сошлись.
Алгоритм бинарного поиска имеет асимптотическую сложность O(log(n)), что делает его очень быстрым для больших массивов. Однако, для небольших массивов или неупорядоченных массивов, другие алгоритмы могут быть более эффективны.
2. Сортировки пузырьком, выбором, вставками
Алгоритмы сортировки – один из фундаментальных инструментов, которые разработчик должен иметь в своем арсенале. Квадратичные сортировки (пузырьком, выбором, вставками) – первое, что следует проработать начинающему разработчику. В случае когда скорость имеет значение, вы вряд ли будете их использовать, но работа с ними является хорошим введением в работу с массивами.
1. Задать массив элементов для сортировки.
2. Начать с первого элемента и проходить по массиву.
3. Сравнить текущий элемент с следующим элементом. Если текущий элемент больше следующего, то поменять их местами.
4. Если была произведена перестановка, перейти на следующий проход по массиву, начиная с первого элемента.
5. Если перестановок не было, то массив уже отсортирован и можно выйти из цикла.
6. Вывести отсортированный массив.
Пример кода на Python:
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
print(bubble_sort(arr))
# выведет [11, 12, 22, 25, 34, 64, 90]
3. Быстрая сортировка и сортировка слиянием
Быстрая сортировка или сортировка Хоара – алгоритм сортировки, основанный на принципе «разделяй и властвуй». Он имеет сложность O(n log n) в среднем и лучшем случае, и сложность O(n^2) в худшем случае, но обычно работает быстрее, чем другие сортировки с такой же сложностью.
Алгоритм сортировки Хоара производит сортировку массива путем разбиения его на две части, которые затем сортируются отдельно друг от друга. Разбиение производится таким образом, что справа от выбранного элемента находятся элементы, которые больше или равны ему, а слева – элементы, меньшие или равные. Затем процесс повторяется рекурсивно для каждой из двух половинок.
Алгоритм быстрой сортировки:
1. Выбираем опорный элемент. Это может быть любой элемент массива, например, первый, последний или средний.
2. Разбиваем массив на две части: элементы, меньше или равные опорному, и элементы, больше опорного.
3. Рекурсивно сортируем каждую из двух половинок.
4. Объединяем отсортированные половинки, помещая элементы меньшие опорного слева от него, а элементы большие опорного – справа.
Простейший код на Python:
def quick_sort(arr):
if len(arr) <= 1:
return arr
else:
pivot = arr[0]
less = [x for x in arr[1:] if x <= pivot]
greater = [x for x in arr[1:] if x > pivot]
return quick_sort(less) + [pivot] + quick_sort(greater)
arr = [3, 7, 2, 8, 4, 1, 6, 9, 5]
print(quick_sort(arr))
# Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]
4. Кодирование Хаффмена
Алгоритм кодирования Хаффмана применяется для сжатия данных и используется во многих архиваторах и программных пакетах. Его работа основана на создании оптимального кода для каждого символа входного сообщения. Алгоритм состоит из нескольких шагов:
1. Определение частоты каждого символа в сообщении.
2. Составление списка частот символов и упорядочивание по возрастанию.
3. Объединение двух символов с наименьшей частотой в новый символ, у которого частота равна сумме частот предыдущих символов.
4. Порождение нового списка частот, в котором новый символ становится одним элементом, а остальные остаются без изменений, и повторение шагов 2 и 3 до тех пор, пока не останется только один элемент в списке.
5. Построение дерева Хаффмана из списка символов, при этом все символы c наибольшей частотой находятся на более высоких уровнях дерева.
6. Правила кодирования: присвоение кода 0 или 1 каждому символу в зависимости от того, на каком уровне дерева он находится. Если символ находится в левой ветви, то добавляем 0 к коду, в противном случае - 1.
7. Составление таблицы символов и соответствующих им кодов.
8. Запись закодированного сообщения, заменяя каждый символ входных данных его кодом из таблицы.
Пример:
Допустим, имеется сообщение: "abbcccdddd". Тогда процесс будет выглядеть так:
1. Частота символов: a - 1, b - 2, c - 3, d - 4.
2. Список частот: a - 1, b - 2, c - 3, d - 4. (упорядоченный по возрастанию)
3. Объединение символов a и b: ab - 3, c - 3, d - 4.
4. Список частот: ab - 3, c - 3, d - 4. (упорядоченный по возрастанию)
5. Построение дерева Хаффмана:
10
/ \
4 6
/ \ / \
d c a,b -
6. Кодирование символов:
a: 0
b: 1 0
c: 1 1 0
d: 1 1 1
7. Таблица символов и кодов:
a: 0
b: 1 0
c: 1 1 0
d: 1 1 1
8. Кодированное сообщение: 0101101111111111.
Таким образом, сообщение "abbcccdddd" было закодировано в более короткое "0101101111111111" с помощью алгоритма кодирования Хаффмана.
5. Поиск в ширину
Алгоритм поиска в ширину (BFS) используется для обхода всех узлов графа (или дерева) в порядке приоритета, начиная с заданного начального узла, путем исследования узлов на все более удаленных уровнях графа.
1. Создайте очередь (queue) и положите в нее начальный узел.
2. Пометьте начальный узел как посещенный.
3. Пока очередь не пуста, повторяйте следующее:
- извлеките из очереди первый элемент
- для каждого соседнего узла, которого еще не посещали, сделайте следующее:
- пометьте узел как посещенный
- добавьте узел в очередь
4. После обхода всех узлов верните список посещенных узлов.
Пример реализации на языке Python:
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
visited.add(start)
while queue:
node = queue.popleft()
print(node)
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
Пример использования:
graph = {
"A": ["B", "C", "D"],
"B": ["E"],
"C": ["F"],
"D": ["G", "H"],
"E": [],
"F": ["I"],
"G": [],
"H": [],
"I": []
bfs(graph, "A")
Результат:
A
B
C
D
E
F
G
H
I
6. Поиск в глубину
Алгоритм поиска в глубину (DFS) - это метод обхода графа, который использует стек для хранения и отслеживания пройденных вершин. Алгоритм работает следующим образом:
1. Выбрать начальную вершину и поместить ее в стек.
2. Пока стек не пуст, извлекать вершину из стека и проверять, была ли она уже посещена. Если нет, отметить ее как посещенную и добавить ее соседей в стек.
3. Если все соседи уже были посещены, удалить вершину из стека.
4. Повторять шаги 2-3, пока не будут посещены все вершины.
Пример реализации на Python:
def DFS(graph, start):
visited = set()
stack = [start]
while stack:
vertex = stack.pop()
if vertex not in visited:
visited.add(vertex)
stack.extend(graph[vertex] - visited)
return visited
Здесь функция `DFS` принимает граф в виде словаря и начальную вершину в качестве аргументов. Для хранения посещенных вершин используется множество `visited`, а для хранения текущего пути - стек `stack`. Внутри цикла извлекается вершина из стека и проверяется, была ли она уже посещена. Если нет, она добавляется в список посещенных и все ее соседи, которые еще не были посещены, добавляются в стек. Если все соседи уже были посещены, вершина удаляется из стека. Алгоритм продолжает выполнение до тех пор, пока в стеке остаются не посещенные вершины.
7. Градиентный спуск
Алгоритм градиентного спуска - это итерационный метод оптимизации, используемый для минимизации функции потерь. Он использует метод градиентного спуска, чтобы двигаться по направлению наискорейшего убывания функции потерь.
1. Инициализируем начальное значение вектора параметров w.
2. Для каждой итерации, вычисляем градиент функции потерь по вектору параметров w.
3. Используя градиент, вычисляем новые значения параметров w.
4. Повторяем шаги 2 и 3, пока не достигнем минимума функции потерь или пока не будет выполнен критерий остановки.
Градиент вычисляется путем нахождения производной функции потерь по каждому параметру w. Для этого используется правило дифференцирования сложной функции.
Новые значения параметров w вычисляются путем вычитания из текущих значений градиента, умноженного на коэффициент обучения alpha.
Алгоритм градиентного спуска является одним из основных методов оптимизации в машинном обучении и используется во многих моделях, таких как линейная регрессия, логистическая регрессия, нейронные сети и др.
8. Алгоритм Дейкстры
Алгоритм Дейкстры (Dijkstra's algorithm) – это алгоритм нахождения пути в графе с неотрицательными весами ребер, который был изобретен нидерландским ученым Эдсгером Дейкстрой. Алгоритм позволяет найти кратчайшие пути от одной вершины графа до всех остальных.
Алгоритм Дейкстры использует множество посещенных вершин и множество непосещенных вершин. Начальная вершина помещается в множество посещенных вершин, затем для каждой непосещенной вершины вычисляется расстояние от начальной вершины до этой вершины. Расстояние определяется как сумма весов ребер от начальной вершины до текущей вершины.
Для выбранной вершины с наименьшим расстоянием выполняются следующие шаги:
1. Проходим по всем смежным вершинам, и если расстояние от начальной вершины до этой смежной вершины меньше, чем текущее значение расстояния до нее, то обновляем значение расстояния.
2. Все смежные вершины добавляем во множество посещенных вершин.
3. Ставим текущую вершину во множество посещенных вершин.
Эти шаги выполняются до тех пор, пока все вершины не будут добавлены во множество посещенных вершин.
После окончания работы алгоритма для каждой вершины графа будет найден кратчайший путь от начальной вершины до нее.
Алгоритм Дейкстры имеет сложность O(N^2), где N – количество вершин в графе, однако существуют и более эффективные алгоритмы поиска кратчайшего пути, например, алгоритм A* или Флойда-Уоршелла.
9. Обмен ключами Диффи-Хеллмана
1. Два пользователи, Alice и Bob, договариваются о двух числах: простом числе p и генераторе g.
2. Оба пользователя выбирают случайные секретные числа: a у Alice и b у Bob.
3. Alice вычисляет g^a mod p и передает Bob'у результат.
4. Bob вычисляет g^b mod p и передает Alice результат.
5. Теперь оба пользователи могут вычислить общий секретный ключ K, используя формулу: K = (g^ab) mod p.
6. Общий ключ K может быть использован в качестве симметричного ключа для зашифровки и расшифровки сообщений между Alice и Bob.
Примечание: Криптографическая прочность алгоритма Диффи-Хеллмана зависит от выбора простого числа p и генератора g. Их выбор и генерация должны проводиться с большой осторожностью, чтобы предотвратить возможные атаки на криптосистему.
Изучение алгоритмов важно не потому, что вам придется в точности их имплементировать в своей работе. Оно важно, потому что учит вас находить подход к задаче.