13. Алгоритмы и структуры данных #

Алгоритмы и структуры данных — фундаментальные концепции программирования, которые позволяют эффективно обрабатывать данные. Python предоставляет как встроенные структуры данных, так и поддержку для реализации сложных алгоритмов.

13.1. Основные структуры данных #

Список (List) #

Список — упорядоченная изменяемая коллекция.

numbers = [1, 2, 3, 4]
numbers.append(5)         # Добавление элемента
numbers.pop(2)            # Удаление элемента по индексу
numbers.sort()            # Сортировка

Кортеж (Tuple) #

Кортеж — упорядоченная неизменяемая коллекция.

coordinates = (10, 20)
print(coordinates[0])  # 10

Множество (Set) #

Множество — неупорядоченная коллекция уникальных элементов.

fruits = {"apple", "banana", "cherry"}
fruits.add("orange")
fruits.remove("banana")

Словарь (Dictionary) #

Словарь — коллекция пар ключ-значение.

grades = {"Alice": 90, "Bob": 85}
grades["Charlie"] = 88
grades.pop("Alice")

Стек (Stack) #

Реализуется с помощью списка, но работает по принципу LIFO (последний вошел — первый вышел).

stack = []
stack.append(1)  # Поместить
stack.append(2)
stack.pop()      # Удалить последний элемент

Очередь (Queue) #

Очередь работает по принципу FIFO (первый вошел — первый вышел).

from collections import deque

queue = deque()
queue.append(1)  # Поместить
queue.append(2)
queue.popleft()  # Удалить первый элемент

13.2. Рекурсия и итерация #

Рекурсия #

Рекурсия — функция вызывает сама себя до достижения базового случая.

def factorial(n):
    if n == 0:
        return 1  # Базовый случай
    return n * factorial(n - 1)  # Рекурсивный случай

print(factorial(5))  # 120

Преимущества рекурсии:

Удобство при работе с задачами, разделяемыми на подзадачи (например, обход деревьев).

Недостатки:

Возможен перерасход памяти из-за глубокого стека вызовов.

Итерация #

Итерация использует циклы для решения задач.

def factorial_iterative(n):
    result = 1
    for i in range(1, n + 1):
        result *= i
    return result

print(factorial_iterative(5))  # 120

13.3. Алгоритмы сортировки и поиска #

Сортировка #

Пузырьковая сортировка (Bubble Sort) #

Простой алгоритм, неэффективный для больших массивов (сложность (O(n^2))).

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([3, 1, 4, 1, 5]))  # [1, 1, 3, 4, 5]

Быстрая сортировка (Quick Sort) #

Эффективный алгоритм со средней сложностью (O(n \log n)).

def quick_sort(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 quick_sort(left) + middle + quick_sort(right)

print(quick_sort([3, 1, 4, 1, 5]))  # [1, 1, 3, 4, 5]

Поиск #

Линейный поиск #

Простой метод поиска элемента с перебором всех элементов (сложность (O(n))).

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

print(linear_search([1, 2, 3, 4], 3))  # 2

Бинарный поиск #

Эффективный алгоритм для отсортированных массивов (сложность (O(\log n))).

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

print(binary_search([1, 2, 3, 4], 3))  # 2