Классификация алгоритмов в Python

Раздел: Python -> Алгоритмы

Типы алгоритмов в Python: обзор и примеры

Python позволяет реализовывать алгоритмы любой сложности. Рассмотрим основные типы: сортировка, поиск, графовые алгоритмы и динамическое программирование. Для каждого типа приведено эффективное решение, альтернативы и возможные проблемы.

Как эффективно отсортировать список чисел в Python?

Сортировка - одна из самых частых операций. Наиболее эффективный способ - использовать быструю сортировку (QuickSort) со средним временем O(n log n).

Быстрая сортировка (QuickSort)

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

алгоритмы и структуры данных python (алгоритмы и структуры данных в python)

[1, 1, 2, 3, 6, 8, 10]

динамическое программирование python (решение задач динамического программирования на python)

Алгоритм выбирает опорный элемент, делит список на три части, рекурсивно сортирует левую и правую части. Встроенная функция sorted() реализует Timsort, который также эффективен.

Альтернативы:

  • Пузырьковая сортировка (O(n^2)) - простой, но медленный алгоритм.
  • Сортировка вставками (O(n^2)) - эффективна для почти отсортированных данных.
  • Использование встроенной sorted() или .sort() - рекомендуется для большинства случаев.
# Пузырьковая сортировка
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

print(bubble_sort([64, 34, 25, 12, 22, 11, 90]))

типы алгоритмов в python (типы алгоритмов в python)

[11, 12, 22, 25, 34, 64, 90]

алгоритм выбора python (алгоритм выбора (selection) на python)

Типичные проблемы:

  • Рекурсия в QuickSort может превысить глубину стека при больших массивах (можно использовать итеративную версию).
  • Пузырьковая сортировка слишком медленная для больших данных.
  • sorted() создает новый список, а .sort() изменяет исходный - путаница может привести к потере данных.

Как выполнить поиск элемента в отсортированном массиве?

Бинарный поиск обеспечивает логарифмическую скорость и является стандартом для отсортированных данных.

Бинарный поиск (итеративная версия)

def binary_search(arr, target):
    left, right = 0, len(arr)-1
    while left <= right:
        mid = (left + right)//2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid+1
        else:
            right = mid-1
    return -1

arr = [2,3,5,7,11,13,17]
print(binary_search(arr, 13))

алгоритм евклида на python (алгоритм евклида на python)

5

квадраты python (вычисление квадратов чисел в python)

Альтернативы:

  • Линейный поиск (O(n)) - работает на неотсортированных данных, но медленнее.
  • Рекурсивный бинарный поиск.
  • Использование модуля bisect для вставки и поиска.
# Линейный поиск
def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

print(linear_search([3,5,7,9], 7))
2

Типичные проблемы:

  • Бинарный поиск требует предварительной сортировки массива; если массив не отсортирован, результат будет неверным.
  • Ошибки при вычислении середины (переполнение целых чисел в некоторых языках, но в Python это не проблема).
  • Не обрабатывается случай пустого массива.

Как найти кратчайший путь во взвешенном графе?

Алгоритм Дейкстры находит кратчайшие пути от начальной вершины до всех остальных в графе с неотрицательными весами.

Алгоритм Дейкстры с использованием кучи

import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # (расстояние, вершина)
    while pq:
        current_dist, current_node = heapq.heappop(pq)
        if current_dist > distances[current_node]:
            continue
        for neighbor, weight in graph[current_node].items():
            distance = current_dist + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))
    return distances

graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
print(dijkstra(graph, 'A'))
{'A': 0, 'B': 1, 'C': 3, 'D': 4}

Другие алгоритмы для графов:

  • Поиск в ширину (BFS) - для невзвешенных графов или поиска кратчайшего пути по количеству ребер.
  • Поиск в глубину (DFS) - для обхода и поиска путей, без гарантии кратчайшего.
  • Алгоритм Беллмана-Форда - для графов с отрицательными весами (но медленнее).
# BFS для невзвешенного графа
from collections import deque

def bfs(graph, start):
    visited = set()
    queue = deque([start])
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            queue.extend(neighbor for neighbor in graph[node] if neighbor not in visited)
    return visited

print(bfs({0:[1,2],1:[2],2:[0,3],3:[3]}, 0))
{0, 1, 2, 3}

Типичные проблемы:

  • Алгоритм Дейкстры не работает с отрицательными весами (используется Беллмана-Форда).
  • Без использования кучи (через простой массив) сложность растет до O(V^2).
  • Рекурсивный DFS может привести к переполнению стека для больших графов.

Как решить задачу о рюкзаке с помощью динамического программирования?

Классическая задача: выбор предметов с максимальной суммарной ценностью при ограниченной вместимости. Динамическое программирование (DP) позволяет решить ее за O(n*W).

Итеративное DP снизу вверх

def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0]*(capacity+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(1, capacity+1):
            if weights[i-1] <= w:
                dp[i][w] = max(dp[i-1][w], dp[i-1][w-weights[i-1]] + values[i-1])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][capacity]

weights = [2,3,4,5]
values = [3,4,5,6]
capacity = 5
print(knapsack(weights, values, capacity))
7

Альтернативные подходы:

  • Рекурсивный перебор (экспоненциальная сложность) - простой для малого n.
  • Мемоизация (рекурсия + кеш) - сочетает простоту рекурсии с эффективностью DP.
  • Жадный алгоритм (например, по удельной ценности) - не гарантирует оптимальность, но быстрее.
# Рекурсивный перебор с мемоизацией
def knapsack_rec(weights, values, capacity, n, memo={}):
    if n == 0 or capacity == 0:
        return 0
    key = (n, capacity)
    if key in memo:
        return memo[key]
    if weights[n-1] > capacity:
        result = knapsack_rec(weights, values, capacity, n-1, memo)
    else:
        result = max(knapsack_rec(weights, values, capacity, n-1, memo),
                     values[n-1] + knapsack_rec(weights, values, capacity-weights[n-1], n-1, memo))
    memo[key] = result
    return result

print(knapsack_rec([2,3,4,5],[3,4,5,6],5,4))
7

Типичные проблемы:

  • Неправильная индексация в DP-таблице (часто путают i и w).
  • Использование рекурсии без мемоизации приводит к экспоненциальному росту.
  • Жадный алгоритм может дать неоптимальный результат (например, если предметы не делятся).

Расширенные примеры алгоритмов

Дополнительные примеры демонстрируют реализацию менее распространенных, но важных алгоритмов.

Сортировка слиянием (Merge Sort)

Пример 
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 = 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.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([38,27,43,3,9,82,10]))
[3, 9, 10, 27, 38, 43, 82]

Сортировка слиянием использует принцип "разделяй и властвуй". Она стабильна и эффективна, но требует O(n) дополнительной памяти.

Поиск подстроки с помощью Z-функции

Пример 
def z_function(s):
    n = len(s)
    z = [0]*n
    l = r = 0
    for i in range(1, n):
        if i <= r:
            z[i] = min(r-i+1, z[i-l])
        while i+z[i] < n and s[z[i]] == s[i+z[i]]:
            z[i] += 1
        if i+z[i]-1 > r:
            l, r = i, i+z[i]-1
    return z

def search_pattern(text, pattern):
    concat = pattern + '$' + text
    z = z_function(concat)
    pattern_len = len(pattern)
    positions = []
    for i in range(pattern_len+1, len(concat)):
        if z[i] == pattern_len:
            positions.append(i - pattern_len - 1)
    return positions

print(search_pattern("abcabcabc", "abc"))
[0, 3, 6]

Z-функция позволяет найти все вхождения образца за O(n+m) времени. Это эффективнее прямого сравнения.

Минимальное остовное дерево: алгоритм Прима

Пример 
import heapq

def prim(graph, start):
    mst = []
    visited = set([start])
    edges = [(weight, start, neighbor) for neighbor, weight in graph[start].items()]
    heapq.heapify(edges)
    while edges:
        weight, u, v = heapq.heappop(edges)
        if v not in visited:
            visited.add(v)
            mst.append((u, v, weight))
            for neighbor, w in graph[v].items():
                if neighbor not in visited:
                    heapq.heappush(edges, (w, v, neighbor))
    return mst

graph = {
    'A': {'B': 1, 'C': 3},
    'B': {'A': 1, 'C': 1, 'D': 4},
    'C': {'A': 3, 'B': 1, 'D': 1},
    'D': {'B': 4, 'C': 1}
}
print(prim(graph, 'A'))
[('A', 'B', 1), ('B', 'C', 1), ('C', 'D', 1)]

Алгоритм Прима находит минимальное остовное дерево. Использует приоритетную очередь для выбора минимального ребра, ведущего к новой вершине.

Ханойские башни (рекурсивный алгоритм)

Пример 
def hanoi(n, source, target, auxiliary):
    if n == 1:
        print(f"Переместить диск 1 с {source} на {target}")
        return
    hanoi(n-1, source, auxiliary, target)
    print(f"Переместить диск {n} с {source} на {target}")
    hanoi(n-1, auxiliary, target, source)

hanoi(3, 'A', 'C', 'B')
Переместить диск 1 с A на C
Переместить диск 2 с A на B
Переместить диск 1 с C на B
Переместить диск 3 с A на C
Переместить диск 1 с B на A
Переместить диск 2 с B на C
Переместить диск 1 с A на C

Задача Ханойских башен - классический пример рекурсии. Количество ходов равно 2^n - 1. Рекурсивный подход элегантен, но при больших n вызовет ошибку переполнения стека.

Типы алгоритмов в Python - comments

En
типы алгоритмов в python (python)