Какая примерная сложность обращения матрицы?

Что проверяют

Знаете ли вы порядок сложности, O(n³), и понимаете ли, что из него следует на практике. Главный уточняющий вопрос: нужно ли вообще обращать матрицу, например в нормальном уравнении линейной регрессии.

Как отвечать

Базовый ответ: обращение матрицы n×n методом Гаусса или через LU-разложение стоит O(n³) операций и O(n²) памяти. Кубический рост означает, что матрица в 10 раз больше обращается примерно в 1000 раз дольше.

Дальше покажите глубину:

• теоретическая граница: обращение по сложности эквивалентно умножению матриц, формально это O(n^ω). Алгоритм Штрассена даёт около n^2.81, лучшие известные оценки ω около 2.37. На практике они не применяются из-за огромных констант: numpy и scipy вызывают LAPACK с кубическими алгоритмами, ускоренными BLAS;
• константа: LU-разложение около 2n³/3 операций, для симметричной положительно определённой матрицы разложение Холецкого вдвое дешевле;
• структура: диагональная обращается за O(n), треугольная система решается за O(n²), трёхдиагональная методом прогонки за O(n). Для больших разреженных матриц берут итеративные методы вроде сопряжённых градиентов;
• ML-контекст: в нормальном уравнении θ = (XᵀX)⁻¹Xᵀy при m объектах и n признаках сборка XᵀX стоит O(mn²), обращение O(n³). При миллионах объектов узким местом часто оказывается сборка, при сотнях тысяч признаков уже обращение, и тогда переходят на градиентные методы.

Ключевая мысль: явная обратная почти никогда не нужна. Для системы Ax = b берут np.linalg.solve, для регрессии np.linalg.lstsq на основе SVD. Это быстрее и численно устойчивее. LinearRegression в scikit-learn тоже решает задачу наименьших квадратов, а не обращает XᵀX.

Где спотыкаются

Называют O(n²), путая сложность с числом элементов, или O(n log n) по аналогии с сортировкой.

Предлагают np.linalg.inv(A) @ b для решения системы. Это лишняя работа и потеря точности на плохо обусловленных матрицах, а число обусловленности XᵀX равно квадрату числа обусловленности X.

Выдают алгоритм Копперсмита и Винограда за то, что работает внутри библиотек. Для реальных размеров это чисто теоретический результат.