В программировании алгоритм — это набор инструкций для решения конкретной проблемы или достижения конкретной задачи. Алгоритмы могут быть написаны на любом языке программирования и могут быть как простыми (последовательность основных операций), так и сложными (многоэтапный процесс, включающий различные структуры данных и логику). Основная цель алгоритма — принять входные данные, обработать их и предоставить ожидаемый результат. Алгоритмы можно классифицировать на основе временной и пространственной сложности, метода, используемого для решения проблемы, и типа решаемой проблемы. Примерами алгоритмов являются сортировка, поиск, обход графа, манипуляции со строками, математические операции и многое другое.
@ai_machinelearning_big_data - машинное обучение в телеграмме.
Алгоритмы, о которых мы будем говорить:
- Алгоритмы сортировки. Сортировка является фундаментальной операцией в компьютерных науках, и для неё существует несколько эффективных алгоритмов, таких как быстрая сортировка, сортировка слиянием и пирамидальная сортировка.
- Алгоритмы поиска. Поиск элемента в большом наборе данных — распространенная задача, и для неё существует несколько эффективных алгоритмов, таких как бинарный поиск и хеш-таблицы.
- Алгоритмы графов. Алгоритмы графов используются для решения задач, связанных с графами, таких как поиск кратчайшего пути между двумя узлами или определение связности графа.
- Динамическое программирование. Динамическое программирование — это метод решения проблем путем их разбиения на более мелкие подзадачи и сохранения решений этих подзадач во избежание избыточных вычислений.
- Жадные алгоритмы. Жадные алгоритмы используются для решения задач оптимизации, делая локально оптимальный выбор на каждом шаге.
- Разделяй и властвуй. Разделяй и властвуй — это парадигма разработки алгоритма, основанная на многоветвящейся рекурсии. Алгоритм «разделяй и властвуй» разбивает проблему на подзадачи того же или родственного типа, пока они не станут достаточно простыми, чтобы их можно было решить напрямую.
- Поиск с возвратом. Это общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М.
- Рандомизированный алгоритм: Рандомизированные алгоритмы используют случайность для решения проблемы. Это может быть полезно для решения проблем, которые не могут быть решены детерминистически, или для повышения средней сложности задачи.
Эти алгоритмы широко используются в различных приложениях, и программисту важно хорошо их понимать. Поэтому я постараюсь объяснить их.
1. Алгоритмы сортировки
Быстрая сортировка: Быстрая сортировка — это алгоритм «разделяй и властвуй», который выбирает «основной» элемент из массива и разбивает остальные элементы на два подмассива. Затем подмассивы сортируются рекурсивно.
def quicksort(arr):
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quicksort(left) + middle + quicksort(right)
print(quicksort([3,6,8,10,1,2,1]))
Сортировка слиянием: Алгоритм сортировки слиянием — это алгоритм «разделяй и властвуй», который делит массив на две части, сортирует две половины, а затем снова объединяет их.
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = 0
j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result += left[i:]
result += right[j:]
return result
print(merge_sort([3,6,8,10,1,2,1]))
Пирамидальная сортировка: Пирамидальная сортировка — это алгоритм сортировки на основе сравнения, который строит пирамиду из входных элементов, а затем многократно извлекает её максимальный элемент и помещает его в конец отсортированного выходного массива.
def heap_sort(arr):
n = len(arr)
for i in range(n, -1, -1):
heapify(arr, n, i)
for i in range(n-1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[i] < arr[l]:
largest = l
if r < n and arr[largest] < arr[r]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
print(heap_sort([3,6,8,10,1,2,1]))
2. Алгоритмы поиска
Бинарный поиск: Бинарный поиск — это эффективный алгоритм поиска элемента в отсортированном списке. Он работает путем многократного деления пополам искомой части массива, пока не будет найдено искомое значение.
def binary_search(arr, x):
low = 0
high = len(arr) - 1
mid = 0
while low <= high:
mid = (high + low) // 2
if arr[mid] < x:
low = mid + 1
elif arr[mid] > x:
high = mid - 1
else:
return mid
return -1
print(binary_search([1,2,3,4,5,6,7], 4))
Хеш-таблицы: Хэш-таблица — это структура данных, которая сопоставляет ключи со значениями, используя хеш-функцию для вычисления индекса в массиве сегментов или слотов, из которых можно найти желаемое значение.
class HashTable:
def __init__(self):
self.size = 10
self.keys = [None] * self.size
self.values = [None] * self.size
def put(self, key, data):
index = self.hash_function(key)
while self.keys[index] is not None:
if self.keys[index] == key:
self.values[index] = data # update
return
index = (index + 1) % self.size
self.keys[index] = key
self.values[index] = data
def get(self, key):
index = self.hash_function(key)
while self.keys[index] is not None:
if self.keys[index] == key:
return self.values[index]
index = (index + 1) % self.size
return None
def hash_function(self, key):
sum = 0
for pos in range(len(key)):
sum = sum + ord(key[pos])
return sum % self.size
t = HashTable()
t.put("apple", 10)
t.put("orange", 20)
t.put("banana", 30)
print(t.get("orange"))
3. Графический алгоритм
Алгоритм Дейкстры: Алгоритм Дейкстры — это алгоритм поиска кратчайшего пути между узлами в графе.
import heapq
def dijkstra(graph, start):
heap = [(0, start)]
visited = set()
while heap:
(cost, v) = heapq.heappop(heap)
if v not in visited:
visited.add(v)
for u, c in graph[v].items():
if u not in visited:
heapq.heappush(heap, (cost + c, u))
return visited
graph = {
'A': {'B': 2, 'C': 3},
'B': {'D': 4, 'E': 5},
'C': {'F': 6},
'D': {'G': 7},
'E': {'G': 8, 'H': 9},
'F': {'H': 10},
'G': {},
'H': {}
}
print(dijkstra(graph, 'A'))
4. Динамическое программирование
Последовательность Фибоначчи: Классическим примером проблемы, которую можно решить с помощью динамического программирования, является последовательность Фибоначчи.
def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
else:
return fibonacci(n-1) + fibonacci(n-2)
print(fibonacci(10))
5. Жадне алгоритмы
Кодирование Хаффмана: Кодирование Хаффмана — это алгоритм сжатия данных, который формулирует основную идею сжатия файлов.
from collections import Counter, namedtuple
def huffman_encoding(data):
"""
Generates a Huffman encoded string of the input data
"""
# Create a frequency counter for the data
freq_counter = Counter(data)
# Create a namedtuple for the Huffman tree nodes
HuffmanNode = namedtuple("HuffmanNode", ["char", "freq"])
# Create a priority queue for the Huffman tree
priority_queue = PriorityQueue()
# Add all characters to the priority queue
for char, freq in freq_counter.items():
priority_queue.put(HuffmanNode(char, freq))
# Combine nodes until only the root node remains
while priority_queue.qsize() > 1:
left_node = priority_queue.get()
right_node = priority_queue.get()
combined_freq = left_node.freq + right_node.freq
combined_node = HuffmanNode(None, combined_freq)
priority_queue.put(combined_node)
# Generate the Huffman code for each character
huffman_code = {}
generate_code(priority_queue.get(), "", huffman_code)
# Encode the input data
encoded_data = ""
for char in data:
encoded_data += huffman_code[char]
return encoded_data, huffman_code
print(huffman_encoding("aaaaabbbcccc"))
6. Разделяй и властвуй
Сортировка слиянием: уже была объяснена выше…
7. Поиск с возвратом
Проблема N-ферзей. Проблема N-ферзей — это классическая проблема, которую можно решить с помощью поиска с возвратом. Цель состоит в том, чтобы разместить N-ферзей на шахматной доске NxN таким образом, чтобы ни один ферзь не мог атаковать другого ферзя.
def solveNQueens(n):
def could_place(row, col):
# check if a queen can be placed on board[row][col]
# check if this row is not under attack from any previous queen in that column
for i in range(row):
if board[i] == col or abs(board[i] - col) == abs(i - row):
return False
return True
def backtrack(row=0, count=0):
for col in range(n):
if could_place(row, col):
board[row] = col
if row + 1 == n:
count += 1
else:
count = backtrack(row + 1, count)
return count
board = [-1 for x in range(n)]
return backtrack()
print(solveNQueens(4))
Этот алгоритм начинает размещать фигуры в первом ряду и для каждого размещённого ферзя проверяет, не атакован ли он каким-либо предыдущим ферзём. Если нет, он переходит к следующей строке и повторяет процесс. Если ферзь находится в позиции, где он подвергается атаке, алгоритм отступает и пробует другую позицию. Это продолжается до тех пор, пока все ферзи не будут размещены на доске, не атакуя друг друга.
8. Рандомизированный алгоритм
Рандомизированная быстрая сортировка: вариант алгоритма быстрой сортировки, в котором точка опоры выбирается случайным образом.
import random
def randomized_quicksort(arr):
if len(arr) <= 1:
return arr
pivot = random.choice(arr)
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return randomized_quicksort(left) + middle + randomized_quicksort(right)
print(randomized_quicksort([3,6,8,10,1,2,1]))
Это некоторые из наиболее часто используемых алгоритмов, с которыми должен быть знаком каждый программист. Понимание этих алгоритмов и их реализации может помочь программисту принимать лучшие решения, когда речь идет о разработке и реализации эффективных решений.