Что такое временная сложность O(N²)?

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

Пример на Python:

def find_all_pairs(arr):
    """Выводит все пары элементов массива. Сложность O(n²)."""
    for i in range(len(arr)):
        for j in range(len(arr)):
            print(f"({arr[i]}, {arr[j]})")

Типичные алгоритмы с O(N²):

• Сортировка пузырьком (Bubble Sort)
• Сортировка выбором (Selection Sort)
• Сортировка вставками (Insertion Sort) в худшем случае
• Проверка всех возможных пар в массиве
• Некоторые наивные реализации алгоритмов на матрицах

Проблема производительности: При больших N (например, 100 000 элементов) количество операций становится огромным (10¹⁰), что делает алгоритм непригодным для production.

Способы оптимизации:

1. Использовать более эффективные алгоритмы: Замена на O(N log N) (быстрая сортировка, сортировка слиянием).
2. Применять хеш-таблицы (словари): Для поиска или проверки существования элемента за O(1).
3. Использовать метод двух указателей: На отсортированных данных некоторые задачи решаются за O(N).