Что такое N-Squared?

Что такое N-Squared (O(N²))?

O(N²) — это нотация, обозначающая квадратичную сложность алгоритма. Это один из самых важных концептов в анализе сложности алгоритмов и computer science.

Определение

O(N²) означает, что при увеличении входных данных в N раз, время выполнения увеличивается в N² раз.

Входные данные: N элементов
Время выполнения пропорционально: N * N = N²

Примеры:
N = 10      → Операции: ~100
N = 100     → Операции: ~10,000
N = 1,000   → Операции: ~1,000,000
N = 10,000  → Операции: ~100,000,000

Примеры алгоритмов с O(N²) сложностью

1. Вложенные циклы (базовый пример)

def nested_loops(arr):
    for i in range(len(arr)):      # N итераций
        for j in range(len(arr)):  # N итераций
            print(arr[i], arr[j])  # O(1) операция

# Всего: N * N = O(N²)

2. Bubble Sort

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):              # N итераций
        for j in range(n - 1):      # N-1 итераций
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

# Сложность: O(N²)

3. Selection Sort

def selection_sort(arr):
    n = len(arr)
    for i in range(n):              # N итераций
        min_idx = i
        for j in range(i + 1, n):  # N-i итераций
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

# Сложность: O(N²)

4. Insertion Sort

def insertion_sort(arr):
    for i in range(1, len(arr)):      # N итераций
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:  # До N итераций
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

# Сложность: O(N²) в худшем случае

5. Матричное умножение (наивный подход)

def matrix_multiply(A, B):
    n = len(A)
    C = [[0] * n for _ in range(n)]
    
    for i in range(n):          # N итераций
        for j in range(n):      # N итераций
            for k in range(n):  # N итераций
                C[i][j] += A[i][k] * B[k][j]
    
    return C

# Сложность: O(N³) даже

Сравнение сложностей

Операции для N элементов:

N      | O(N)    | O(N log N) | O(N²)      | O(N³)
-------|---------|-----------|----------|----------
10     | 10      | 33        | 100      | 1,000
100    | 100     | 664       | 10,000   | 1,000,000
1,000  | 1,000   | 9,965     | 1,000,000| 1,000,000,000
10,000 | 10,000  | 132,877   | 100,000,000| (Too much)

Проблемы с O(N²)

При N = 10,000:

Если каждая операция = 1 наносекунда:
O(N²) = 100,000,000 операций = 100 миллисекунд (медленно)

При N = 1,000,000:
O(N²) = 10^12 операций = 1,000 секунд ≈ 17 минут (неприемлемо!)

Оптимизация O(N²) алгоритмов

Вместо Bubble Sort (O(N²)) → Merge Sort (O(N log N))

# Медленно: Bubble Sort O(N²)
def bubble_sort(arr):
    # ... N² операций

# Быстро: Merge Sort O(N log N)
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)

# Результат: для N=10,000
# Bubble Sort: 100 млн операций
# Merge Sort: 132,877 операций
# Ускорение: 750x!

Когда O(N²) приемлемо?

1. N < 1,000 — обычно ОК
2. N < 10,000 — может быть, если операции быстрые
3. N > 100,000 — обычно неприемлемо без оптимизации

В контексте Machine Learning

K-Nearest Neighbors (KNN)

# Наивный KNN: O(N²) при поиске соседей
def knn_naive(X_train, X_test, k):
    for each sample in X_test:  # N_test
        distances = []
        for each point in X_train:  # N_train
            dist = euclidean_distance(sample, point)
            distances.append(dist)
        # O(N_train * N_test) = O(N²)

Оптимизация: использовать KD-Tree

# KD-Tree: O(N log N) для построения + O(log N) для запроса
from sklearn.neighbors import KDTree
tree = KDTree(X_train)
distances, indices = tree.query(X_test, k=k)
# O(N log N + M log N) где M = N_test

Вывод из анализа сложности

def analyze_complexity():
    # Плохо: две вложенные loops для сортировки
    # O(N²) → медленно для N > 10,000
    
    # Хорошо: использовать встроенный sort
    arr.sort()  # O(N log N) → быстро
    
    # Лучше: использовать подходящую структуру данных
    # Для поиска в sorted data:
    bisect.bisect(arr, target)  # O(log N) → очень быстро

Практическое правило

Если видишь два вложенных цикла обходящих одну и ту же коллекцию:
→ Это вероятно O(N²)
→ Подумай, можно ли оптимизировать

Вопросы для оптимизации:
1. Нужны ли мне два полных цикла?
2. Можно ли использовать hash table/set для O(1) lookup?
3. Можно ли отсортировать и использовать binary search?
4. Есть ли готовый оптимизированный алгоритм?

Заключение

O(N²) — это значимая сложность, которая работает для малых N но становится неприемлемой для больших. В production коде всегда анализируй сложность алгоритмов и оптимизируй когда возможно. Разница между O(N²) и O(N log N) может быть 1000x ускорение!