Как определить сложность задачи?

Как определить сложность задачи

Определение сложности задачи критично для планирования, оценки времени, выделения ресурсов и управления рисками. Существует несколько подходов, которые применяются в зависимости от контекста.

1. Big O нотация (Временная и пространственная сложность)

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

# O(1) — Константная сложность
def get_first_element(arr: list) -> any:
    return arr[0]  # Всегда одна операция

# O(n) — Линейная сложность
def find_element(arr: list, target: any) -> bool:
    for item in arr:  # Проходит до n элементов
        if item == target:
            return True
    return False

# O(n²) — Квадратичная сложность
def bubble_sort(arr: list) -> list:
    n = len(arr)
    for i in range(n):
        for j in range(n - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# O(log n) — Логарифмическая сложность
def binary_search(arr: list, target: any) -> int:
    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

# O(n log n) — Логарифмическая линейная сложность (хорошие сортировки)
def merge_sort(arr: list) -> list:
    if len(arr) <= 1:
        return arr
    
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    
    return merge(left, right)

# O(2^n) — Экспоненциальная сложность (очень плохо)
def fibonacci(n: int) -> int:
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)  # Без мемоизации!

# O(n!) — Факториальная сложность (крайне неэффективно)
def generate_permutations(arr: list) -> list:
    if len(arr) <= 1:
        return [arr]
    
    perms = []
    for i in range(len(arr)):
        rest = arr[:i] + arr[i+1:]
        for perm in generate_permutations(rest):
            perms.append([arr[i]] + perm)
    return perms

Таблица Big O в порядке эффективности:

2. Анализ задачи: вопросы для себя

Когда встречаешь новую задачу, задай себе эти вопросы:

Вопросы про масштаб:

• Сколько данных нужно обработать? (n < 1000? < 1,000,000? > 1,000,000,000?)
• Какие ограничения памяти? (в памяти или потоком?)
• Какое время выполнения допустимо? (секунды? миллисекунды?)

Вопросы про зависимости:

• Есть ли зависимости от других систем? (БД, API, файловая система?)
• Нужна ли синхронизация с другими процессами?
• Есть ли блокирующие операции?

Вопросы про неопределённость:

• Есть ли неясные требования?
• Могут ли требования меняться?
• Есть ли неизвестные технические риски?

# Пример анализа задачи
class TaskAnalyzer:
    def analyze(self, task_description: str) -> dict:
        return {
            "data_volume": self._estimate_data_volume(),
            "algorithmic_complexity": self._estimate_algorithm_complexity(),
            "dependencies": self._identify_dependencies(),
            "uncertainty": self._estimate_uncertainty(),
            "total_complexity": self._calculate_total_complexity()
        }
    
    def _estimate_data_volume(self) -> str:
        """Оценка объёма данных"""
        # Анализируем задачу
        return "low | medium | high | very_high"
    
    def _estimate_algorithm_complexity(self) -> str:
        """Сложность алгоритма"""
        return "O(1) | O(log n) | O(n) | O(n log n) | O(n²) | O(2^n)"
    
    def _identify_dependencies(self) -> list:
        """Внешние зависимости"""
        return ["database", "api", "filesystem", "network"]
    
    def _estimate_uncertainty(self) -> str:
        """Уровень неопределённости"""
        return "low | medium | high"
    
    def _calculate_total_complexity(self) -> int:
        """Общая сложность (от 1 до 10)"""
        return 5

3. Практическая оценка сложности

Пример 1: Поиск дубликатов в массиве

# ❌ Наивный подход — O(n²)
def has_duplicates_naive(arr: list[int]) -> bool:
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] == arr[j]:
                return True
    return False

# ✅ Оптимальный подход — O(n)
def has_duplicates_optimal(arr: list[int]) -> bool:
    seen = set()
    for num in arr:
        if num in seen:
            return True
        seen.add(num)
    return False

# Различие в производительности при n=10000:
# Наивный: ~100,000,000 операций (~10-20 сек)
# Оптимальный: ~10,000 операций (~0.001 сек)

Пример 2: Работа с БД

from sqlalchemy.orm import Session
from typing import List

class UserRepository:
    def __init__(self, db: Session):
        self.db = db
    
    # ❌ Плохо: N+1 проблема — O(n) запросов
    def get_users_with_posts_bad(self) -> List[dict]:
        users = self.db.query(User).all()  # 1 запрос
        result = []
        for user in users:  # N запросов
            posts = self.db.query(Post).filter(Post.user_id == user.id).all()
            result.append({"user": user, "posts": posts})
        return result
    
    # ✅ Хорошо: Eager loading — O(1) запрос
    def get_users_with_posts_good(self) -> List[dict]:
        from sqlalchemy.orm import joinedload
        users = self.db.query(User).options(
            joinedload(User.posts)  # Один запрос с JOIN
        ).all()
        return [{"user": u, "posts": u.posts} for u in users]

4. Оценка сложности в контексте проекта

Шкала сложности для разработки (Story Points):

class ComplexityMatrix:
    """Матрица для оценки сложности задачи"""
    
    ASSESSMENT = {
        "data_volume": {
            "trivial": 1,        # < 100 элементов
            "small": 2,          # 100-1000
            "medium": 3,         # 1000-100k
            "large": 5,          # 100k-1M
            "huge": 8,           # > 1M
        },
        "algorithm_complexity": {
            "O(1)": 1,
            "O(log n)": 1,
            "O(n)": 2,
            "O(n log n)": 2,
            "O(n²)": 3,
            "O(2^n)": 5,
        },
        "dependencies": {
            "none": 0,
            "api": 2,
            "database": 2,
            "multiple": 5,
        },
        "uncertainty": {
            "clear": 0,
            "some": 2,
            "high": 5,
        }
    }
    
    def estimate(self, task: dict) -> int:
        """Итоговая оценка в Story Points"""
        score = (
            self.ASSESSMENT["data_volume"][task["data_volume"]] +
            self.ASSESSMENT["algorithm_complexity"][task["algorithm"]] +
            self.ASSESSMENT["dependencies"][task["dependencies"]] +
            self.ASSESSMENT["uncertainty"][task["uncertainty"]]
        )
        return min(score, 21)  # Максимум 21 (fibonacci)

# Примеры оценок
task1 = {
    "name": "Добавить email поле",
    "data_volume": "small",
    "algorithm": "O(1)",
    "dependencies": "database",
    "uncertainty": "clear"
}
# Оценка: 2 + 1 + 2 + 0 = 5 points

task2 = {
    "name": "Рекомендательная система с ML",
    "data_volume": "huge",
    "algorithm": "O(n²)",
    "dependencies": "multiple",
    "uncertainty": "high"
}
# Оценка: 8 + 3 + 5 + 5 = 21 points

5. Инструменты для анализа сложности

import time
from functools import wraps
from typing import Callable

def measure_complexity(func: Callable) -> Callable:
    """Декоратор для измерения временной сложности"""
    @wraps(func)
    def wrapper(*args, **kwargs):
        start = time.perf_counter()
        result = func(*args, **kwargs)
        elapsed = time.perf_counter() - start
        
        n = len(args[0]) if args and hasattr(args[0], "__len__") else "?"
        print(f"{func.__name__}(n={n}): {elapsed:.6f}s")
        return result
    return wrapper

@measure_complexity
def process_data(data: list):
    return sorted(data)  # O(n log n)

# Использование
process_data(list(range(10000)))
# process_data(n=10000): 0.002341s

6. Алгоритмическое мышление

# Задача: Найти два числа, сумма которых равна target

# ❌ Наивный подход — O(n²)
def find_pair_naive(arr: list[int], target: int) -> tuple:
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            if arr[i] + arr[j] == target:
                return (arr[i], arr[j])
    return None

# ✅ Оптимальный подход — O(n)
def find_pair_optimal(arr: list[int], target: int) -> tuple:
    seen = set()
    for num in arr:
        complement = target - num
        if complement in seen:
            return (complement, num)
        seen.add(num)
    return None

# ✅ Альтернатива с двумя указателями — O(n log n) если нужна сортировка
def find_pair_two_pointers(arr: list[int], target: int) -> tuple:
    arr = sorted(arr)
    left, right = 0, len(arr) - 1
    while left < right:
        total = arr[left] + arr[right]
        if total == target:
            return (arr[left], arr[right])
        elif total < target:
            left += 1
        else:
            right -= 1
    return None

Резюме: Как определить сложность

1. Анализ входных данных:

• Размер: n < 1000? < 1,000,000? > 1,000,000,000?
• Структура: массив, граф, дерево?
• Ограничения памяти

2. Анализ алгоритма:

• Сколько циклов? (O(n), O(n²), O(2^n)?)
• Есть ли поиск? (O(log n), O(n)?)
• Используется ли дополнительная память? (O(1), O(n)?)

3. Практические факторы:

• Внешние зависимости (БД, API)
• Синхронизация и конкурентность
• Требования по времени выполнения

4. Итоговая оценка (Story Points):

• Комбинируй алгоритмическую сложность
• Добавь баллы за зависимости
• Добавь баллы за неопределённость
• Результат: 1-21 points

Опыт приходит с практикой. Начни анализировать каждую задачу систематически!