8 лучших алгоритмов, которые должен знать каждый программист

В программировании алгоритм — это набор инструкций для решения конкретной проблемы или достижения конкретной задачи. Алгоритмы могут быть написаны на любом языке программирования и могут быть как простыми (последовательность основных операций), так и сложными (многоэтапный процесс, включающий различные структуры данных и логику). Основная цель алгоритма — принять входные данные, обработать их и предоставить ожидаемый результат. Алгоритмы можно классифицировать на основе временной и пространственной сложности, метода, используемого для решения проблемы, и типа решаемой проблемы. Примерами алгоритмов являются сортировка, поиск, обход графа, манипуляции со строками, математические операции и многое другое.

Алгоритмы, о которых мы будем говорить:

Алгоритмы сортировки. Сортировка является фундаментальной операцией в компьютерных науках, и для неё существует несколько эффективных алгоритмов, таких как быстрая сортировка, сортировка слиянием и пирамидальная сортировка.
Алгоритмы поиска. Поиск элемента в большом наборе данных — распространенная задача, и для неё существует несколько эффективных алгоритмов, таких как бинарный поиск и хеш-таблицы.
Алгоритмы графов. Алгоритмы графов используются для решения задач, связанных с графами, таких как поиск кратчайшего пути между двумя узлами или определение связности графа.
Динамическое программирование. Динамическое программирование — это метод решения проблем путем их разбиения на более мелкие подзадачи и сохранения решений этих подзадач во избежание избыточных вычислений.
Жадные алгоритмы. Жадные алгоритмы используются для решения задач оптимизации, делая локально оптимальный выбор на каждом шаге.
Разделяй и властвуй. Разделяй и властвуй — это парадигма разработки алгоритма, основанная на многоветвящейся рекурсии. Алгоритм «разделяй и властвуй» разбивает проблему на подзадачи того же или родственного типа, пока они не станут достаточно простыми, чтобы их можно было решить напрямую.
Поиск с возвратом. Это общий метод нахождения решений задачи, в которой требуется полный перебор всех возможных вариантов в некотором множестве М.
Рандомизированный алгоритм: Рандомизированные алгоритмы используют случайность для решения проблемы. Это может быть полезно для решения проблем, которые не могут быть решены детерминистически, или для повышения средней сложности задачи.

Эти алгоритмы широко используются в различных приложениях, и программисту важно хорошо их понимать. Поэтому я постараюсь объяснить их.

Быстрая сортировка: Быстрая сортировка — это алгоритм «разделяй и властвуй», который выбирает «основной» элемент из массива и разбивает остальные элементы на два подмассива. Затем подмассивы сортируются рекурсивно.

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]))

Бинарный поиск: Бинарный поиск — это эффективный алгоритм поиска элемента в отсортированном списке. Он работает путем многократного деления пополам искомой части массива, пока не будет найдено искомое значение.

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"))

Алгоритм Дейкстры: Алгоритм Дейкстры — это алгоритм поиска кратчайшего пути между узлами в графе.

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'))

Последовательность Фибоначчи: Классическим примером проблемы, которую можно решить с помощью динамического программирования, является последовательность Фибоначчи.

def fibonacci(n): if n <= 0: return 0 elif n == 1: return 1 else: return fibonacci(n-1) + fibonacci(n-2) print(fibonacci(10))

Кодирование Хаффмана: Кодирование Хаффмана — это алгоритм сжатия данных, который формулирует основную идею сжатия файлов.

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"))

Сортировка слиянием: уже была объяснена выше...

Проблема 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))

Этот алгоритм начинает размещать фигуры в первом ряду и для каждого размещённого ферзя проверяет, не атакован ли он каким-либо предыдущим ферзём. Если нет, он переходит к следующей строке и повторяет процесс. Если ферзь находится в позиции, где он подвергается атаке, алгоритм отступает и пробует другую позицию. Это продолжается до тех пор, пока все ферзи не будут размещены на доске, не атакуя друг друга.

Рандомизированная быстрая сортировка: вариант алгоритма быстрой сортировки, в котором точка опоры выбирается случайным образом.

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]))

Это некоторые из наиболее часто используемых алгоритмов, с которыми должен быть знаком каждый программист. Понимание этих алгоритмов и их реализации может помочь программисту принимать лучшие решения, когда речь идет о разработке и реализации эффективных решений.

Статья была взята из этого источника:

uproger.com

8 лучших алгоритмов, которые должен знать каждый программист

8 лучших алгоритмов, которые должен знать каждый программист

1. Алгоритмы сортировки

2. Алгоритмы поиска

3. Графический алгоритм

4. Динамическое программирование

5. Жадне алгоритмы

6. Разделяй и властвуй

7. Поиск с возвратом

8. Рандомизированный алгоритм