Изучал ли классические алгоритмы

Классические алгоритмы

Да, я активно изучал и регулярно применяю классические алгоритмы в своей работе. Знание алгоритмов — это не просто для собеседований, это необходимый инструмент для написания эффективного кода и решения сложных задач.

Почему я изучал алгоритмы

1. Оптимизация производительности

# ❌ Плохо: наивный алгоритм O(n²)
def find_duplicates_slow(numbers):
    duplicates = []
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] == numbers[j]:
                duplicates.append(numbers[i])
    return duplicates

# На 1 млн элементов: ~1 триллион операций!

# ✅ Хорошо: оптимизированный алгоритм O(n)
def find_duplicates_fast(numbers):
    seen = set()
    duplicates = set()
    for num in numbers:
        if num in seen:
            duplicates.add(num)
        seen.add(num)
    return list(duplicates)

# На 1 млн элементов: ~2 млн операций
# В 500,000 раз быстрее!

2. Решение сложных задач

# Динамическое программирование: числа Фибоначчи

# ❌ Наивная рекурсия: O(2^n)
def fib_slow(n):
    if n <= 1:
        return n
    return fib_slow(n-1) + fib_slow(n-2)

fib_slow(50)  # Занимает минуты

# ✅ Динамическое программирование: O(n)
def fib_fast(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

fib_fast(50)  # Мгновенно

Основные алгоритмы, которые я знаю

1. Сортировка

QuickSort: O(n log n) в среднем

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)

result = quicksort([3, 1, 4, 1, 5, 9, 2, 6])
# [1, 1, 2, 3, 4, 5, 6, 9]

MergeSort: O(n log n) гарантировано

def mergesort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = mergesort(arr[:mid])
    right = mergesort(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

2. Поиск

Бинарный поиск: O(log n)

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

result = binary_search([1, 3, 5, 7, 9], 5)  # 2

3. Графы

DFS (Depth-First Search)

def dfs(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    print(start)
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)
    return visited

graph = {
    1: [2, 3],
    2: [1, 4],
    3: [1, 5],
    4: [2],
    5: [3]
}

dfs(graph, 1)  # 1 2 4 3 5

BFS (Breadth-First Search)

from collections import deque

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

bfs(graph, 1)  # [1, 2, 3, 4, 5]

Dijkstra: поиск кратчайшего пути

import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]
    
    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)
        
        if current_distance > distances[current_node]:
            continue
        
        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, neighbor))
    
    return distances

graph = {
    'A': [('B', 4), ('C', 2)],
    'B': [('A', 4), ('C', 1), ('D', 5)],
    'C': [('A', 2), ('B', 1), ('D', 8)],
    'D': [('B', 5), ('C', 8)]
}

dijkstra(graph, 'A')
# {'A': 0, 'B': 3, 'C': 2, 'D': 8}

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

LCS (Longest Common Subsequence)

def lcs(text1, text2):
    m, n = len(text1), len(text2)
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if text1[i-1] == text2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

result = lcs('abcde', 'ace')
# 3 (подпоследовательность 'ace')

Knapsack Problem (Задача о рюкзаке)

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(capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(
                    values[i-1] + dp[i-1][w - weights[i-1]],
                    dp[i-1][w]
                )
            else:
                dp[i][w] = dp[i-1][w]
    
    return dp[n][capacity]

weights = [1, 3, 4, 5]
values = [1, 4, 5, 7]
capacity = 7

result = knapsack(weights, values, capacity)  # 11

5. Строки (String Algorithms)

KMP (Knuth-Morris-Pratt): поиск подстроки

def build_lps(pattern):
    m = len(pattern)
    lps = [0] * m
    length = 0
    i = 1
    
    while i < m:
        if pattern[i] == pattern[length]:
            length += 1
            lps[i] = length
            i += 1
        else:
            if length != 0:
                length = lps[length - 1]
            else:
                lps[i] = 0
                i += 1
    return lps

def kmp_search(text, pattern):
    n = len(text)
    m = len(pattern)
    lps = build_lps(pattern)
    i = j = 0
    
    while i < n:
        if pattern[j] == text[i]:
            i += 1
            j += 1
        if j == m:
            return i - j  # Найдена подстрока
        elif i < n and pattern[j] != text[i]:
            if j != 0:
                j = lps[j - 1]
            else:
                i += 1
    return -1

result = kmp_search('ABABDABACDABABCABAB', 'ABABCABAB')
# 10

Как я применяю алгоритмы в работе

1. Оптимизация запросов к БД

# ❌ Плохо: N+1 query problem
users = User.query.all()
for user in users:  # N queries
    print(user.posts)  # +1 query per user

# ✅ Хорошо: Eager loading
users = User.query.options(joinedload(User.posts)).all()
# 1 query

2. Кэширование (Hash Tables / Set)

# ❌ Плохо: O(n) поиск
def find_intersection_slow(list1, list2):
    return [x for x in list1 if x in list2]  # O(n*m)

# ✅ Хорошо: O(n+m) с использованием set
def find_intersection_fast(list1, list2):
    set2 = set(list2)
    return [x for x in list1 if x in set2]  # O(n+m)

3. Пагинация (поиск)

# Binary search для поиска страницы
def find_page(total_items, page_size, target_item_id):
    left, right = 1, (total_items + page_size - 1) // page_size
    while left <= right:
        mid = (left + right) // 2
        first_item = (mid - 1) * page_size + 1
        last_item = mid * page_size
        if target_item_id < first_item:
            right = mid - 1
        elif target_item_id > last_item:
            left = mid + 1
        else:
            return mid

4. Сортировка данных

# Встроенная сортировка использует Timsort (O(n log n))
users_sorted = sorted(users, key=lambda u: u.created_at)

# Для больших наборов — используем внешнюю сортировку
import heapq
merged = heapq.merge(
    sorted_chunk1,
    sorted_chunk2,
    sorted_chunk3
)

Алгоритмы в системном дизайне

Rate Limiting (Token Bucket Algorithm)

import time
from collections import deque

class RateLimiter:
    def __init__(self, rate, capacity):
        self.rate = rate  # tokens per second
        self.capacity = capacity
        self.tokens = capacity
        self.last_update = time.time()
    
    def allow_request(self):
        now = time.time()
        elapsed = now - self.last_update
        self.tokens = min(
            self.capacity,
            self.tokens + elapsed * self.rate
        )
        self.last_update = now
        
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

limiter = RateLimiter(rate=10, capacity=100)
for i in range(150):
    if limiter.allow_request():
        print(f'Request {i} allowed')

Мой подход к алгоритмам

Я не зазубриваю алгоритмы, я:

1. Понимаю идею — DFS/BFS, разделяй и властвуй, динамическое программирование
2. Анализирую сложность — Big O notation, лучший/средний/худший случаи
3. Применяю при надобности — когда наивный алгоритм слишком медленный
4. Использую библиотеки — Python's built-in sorted() достаточно умный
5. Профилирую реальный код — не оптимизирую впустую

Ресурсы для изучения

• LeetCode: более 2000 задач
• HackerRank: структурированное обучение
• Книга "Introduction to Algorithms" (CLRS)
• VisuAlgo.net: визуализация алгоритмов
• Big O Cheat Sheet: справочник по сложности

Практический пример из production

# Оптимизация поиска пользователя по email

# ❌ Было: O(n) поиск по каждому запросу
class UserService:
    def find_by_email(self, email):
        for user in self.users:
            if user.email == email:
                return user
        return None

# ✅ Стало: O(1) с индексом (хеш таблица)
class UserService:
    def __init__(self):
        self.users = []
        self.email_index = {}  # email -> user
    
    def add_user(self, user):
        self.users.append(user)
        self.email_index[user.email] = user
    
    def find_by_email(self, email):
        return self.email_index.get(email)

# На 1 млн пользователей: 1 млн → 1 операция

Итоговое резюме

Я изучал и применяю классические алгоритмы потому что:

1. Производительность — правильный алгоритм может ускорить систему в 1000 раз
2. Масштабируемость — O(n) и O(n²) работают по-разному на больших данных
3. Профессионализм — разработчик должен уметь анализировать сложность
4. Интересно — решение алгоритмических задач развивает мышление
5. Собеседования — требуют знаний основных алгоритмов

Но помни:

• Сначала пиши просто и понятно
• Профилируй перед оптимизацией
• Используй встроенные оптимизированные функции
• Не переусложняй без причины