Что показывает сложность по времени алгоритма?

Time Complexity (Сложность по времени алгоритма)

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

Что показывает Big-O notation?

Big-O — это худший случай

Показывает как растёт время выполнения при увеличении входных данных:

O(1)     — Constant time (как n = 1 миллион или 10)
O(log n) — Logarithmic (двоичный поиск)
O(n)     — Linear (простой цикл)
O(n log n) — Linearithmic (хороший сортировщик)
O(n²)    — Quadratic (вложенные циклы)
O(n³)    — Cubic (очень редко используется)
O(2^n)   — Exponential (очень медленно!)
O(n!)    — Factorial (экстремально медленно!)

Визуально: как растёт время

import math

# n = 1000 элементов
n = 1000

time_complexity = {
    "O(1)": 1,                           # 1 операция
    "O(log n)": math.log2(n),            # ~10 операций
    "O(n)": n,                           # 1,000 операций
    "O(n log n)": n * math.log2(n),      # ~10,000 операций
    "O(n²)": n**2,                       # 1,000,000 операций
    "O(n³)": n**3,                       # 1,000,000,000 операций
    "O(2^n)": 2**n,                      # НЕВОЗМОЖНО ВЫЧИСЛИТЬ
}

# При n = 1,000,000
# O(1): 1 операция
# O(n): 1,000,000 операций
# O(n²): 1,000,000,000,000 операций (НИКОГДА не закончится)

Примеры с кодом

1. O(1) — Constant Time

# Доступ к элементу массива
def get_first_element(array):
    return array[0]  # Всегда 1 операция, не зависит от n

# Операция со словарём (lookup по ключу)
def get_user(users_dict, user_id):
    return users_dict[user_id]  # O(1) в среднем случае

# Пример
array = list(range(1_000_000))
result = get_first_element(array)  # Мгновенно

2. O(log n) — Logarithmic

Время удваивается когда размер увеличивается в 4 раза.

# Двоичный поиск
def binary_search(sorted_array, target):
    left, right = 0, len(sorted_array) - 1
    
    while left <= right:
        mid = (left + right) // 2
        if sorted_array[mid] == target:
            return mid
        elif sorted_array[mid] < target:
            left = mid + 1  # Исключаем половину
        else:
            right = mid - 1  # Исключаем половину
    
    return -1  # Не найдено

# Пример
arr = list(range(1_000_000))
found_idx = binary_search(arr, 500_000)
# В худшем случае: log2(1,000,000) ≈ 20 сравнений!

3. O(n) — Linear

Время растёт прямо пропорционально n.

# Простой поиск
def linear_search(array, target):
    for i in range(len(array)):  # Один цикл
        if array[i] == target:
            return i
    return -1

# Сумма всех элементов
def sum_array(array):
    total = 0
    for num in array:  # n итераций
        total += num
    return total

# Пример
arr = list(range(1_000_000))
result = sum_array(arr)  # ~1,000,000 операций

4. O(n log n) — Linearithmic

Оптимальная сложность для сортировки (не основанной на сравнении).

# Merge Sort
def merge_sort(array):
    if len(array) <= 1:
        return array  # Base case: O(1)
    
    mid = len(array) // 2
    left = merge_sort(array[:mid])     # Рекурсия
    right = merge_sort(array[mid:])    # Рекурсия
    
    return merge(left, right)  # O(n) для merge

# Глубина рекурсии: log n
# На каждом уровне: O(n) работы
# Итого: O(n log n)

# Пример
arr = list(range(1_000_000, 0, -1))  # Обратно отсортирован
sorted_arr = merge_sort(arr)
# ~10,000,000 операций (manageable)

5. O(n²) — Quadratic

Вложенные циклы. Очень медленно для больших данных.

# Bubble Sort
def bubble_sort(array):
    n = len(array)
    for i in range(n):           # Внешний цикл: n итераций
        for j in range(n-1):     # Внутренний цикл: n итераций
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

# Проверка всех пар
def has_duplicate_pair_sum(array, target):
    n = len(array)
    for i in range(n):           # n итераций
        for j in range(i+1, n):  # n итераций
            if array[i] + array[j] == target:
                return True
    return False

# Пример
arr = list(range(1_000))
result = bubble_sort(arr)
# 1,000,000 операций (медленно, но терпимо)

arr = list(range(10_000))
result = bubble_sort(arr)
# 100,000,000 операций (очень медленно)

6. O(2^n) — Exponential

Очень медленно! Избегать в production.

# Fibonacci (наивный подход)
def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n-1) + fib_naive(n-2)  # 2 рекурсивных вызова!

# Каждый вызов порождает 2 вызова
# Уровень 0: 1 вызов
# Уровень 1: 2 вызова
# Уровень 2: 4 вызова
# Уровень n: 2^n вызовов

# Пример
fib_naive(50)  # НИКОГДА не закончится!

# С мемоизацией (кэш): O(n)
def fib_memo(n, cache={}):
    if n in cache:
        return cache[n]
    if n <= 1:
        return n
    cache[n] = fib_memo(n-1, cache) + fib_memo(n-2, cache)
    return cache[n]

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

Как анализировать сложность

Правило 1: Игнорируем константы

# O(2n) = O(n)
# O(5n) = O(n)
# O(n/2) = O(n)

def process(array):
    for item in array:     # n итераций
        print(item)
    for item in array:     # ещё n итераций
        print(item)
    # Всего 2n, но Big-O = O(n)

Правило 2: Берём самый быстрый растущий член

# O(n² + n + 1) = O(n²)
# O(n log n + n) = O(n log n)
# O(2^n + n) = O(2^n)

def complex_algo(array):
    # O(n²) вложенные циклы
    for i in range(len(array)):
        for j in range(len(array)):
            pass
    
    # O(n) простой цикл
    for item in array:
        pass
    
    # O(1) константа
    x = 1 + 1
    
    # Итого: O(n²)

Правило 3: Сложение vs Умножение

# Последовательные операции: СКЛАДЫВАЕМ
def sequential(array):
    for item in array:      # O(n)
        pass
    for item in array:      # O(n)
        pass
    # Всего: O(n) + O(n) = O(n)

# Вложенные операции: УМНОЖАЕМ
def nested(array):
    for item in array:          # n итераций
        for item2 in array:     # n итераций
            pass
    # Всего: O(n) × O(n) = O(n²)

Сравнение алгоритмов

algorithm_comparison = {
    "Binary Search": "O(log n) - очень быстро",
    "Quick Sort": "O(n log n) - хороший выбор",
    "Merge Sort": "O(n log n) - стабильный, гарантирован",
    "Heap Sort": "O(n log n) - in-place, хороший",
    "Bubble Sort": "O(n²) - избегать для больших данных",
    "Insertion Sort": "O(n²) - OK для малых данных (< 50 элементов)",
    "Selection Sort": "O(n²) - редко используется",
    "Naive Fibonacci": "O(2^n) - НИКОГДА не используй",
    "Fibonacci with memo": "O(n) - хороший пример optimization"
}

Практические советы

1. Для интервью/собеседования

analysis_checklist = [
    "Определи размер входа (что такое n?)",
    "Сколько раз выполняется основная операция?",
    "Есть ли циклы? Вложенные циклы?",
    "Есть ли рекурсия? Какова глубина?",
    "Игнорируй константы и малые члены",
    "Проверь best, average и worst case",
    "Подумай о Space Complexity тоже"
]

2. Space Complexity (сложность по памяти)

# Часто о нём забывают, но это важно!

# O(1) - используем фиксированное количество переменных
def min_element(array):
    min_val = array[0]
    for item in array:
        min_val = min(min_val, item)
    return min_val

# O(n) - создаём новый массив размером n
def copy_array(array):
    new_array = []
    for item in array:
        new_array.append(item)
    return new_array

# O(log n) - рекурсия в глубину log n
def binary_search_recursive(array, target, left, right):
    # каждый recursive frame занимает память
    pass

Когда что использовать

when_to_use = {
    "n < 10": "Любой алгоритм работает",
    "n < 1,000": "O(n²) допустимо",
    "n < 1,000,000": "O(n log n) хороший выбор",
    "n > 1,000,000": "O(n) или лучше",
    "Real-time (< 100ms)": "O(log n) или O(1)",
    "Streaming data (миллионы в секунду)": "O(1) обязательно"
}

Итог

Time Complexity показывает:

• Как растёт время выполнения с увеличением входных данных
• Масштабируемость алгоритма
• Будет ли это работать для больших данных

Лучшие алгоритмы для production:

1. O(1) — hash table lookup
2. O(log n) — binary search
3. O(n) — linear scan, traversal
4. O(n log n) — быстрая сортировка

Избегай в production:

• O(2^n) — экспоненциальная
• O(n!) — факториальная
• O(n³) и хуже — если данные большие