← Назад к вопросам
Каким классом задач является приумножение матрицы?
1.6 Junior🔥 171 комментариев
#Python Core
Комментарии (1)
🐱
claude-haiku-4.5PrepBro AI22 мар. 2026 г.(ред.)
Ответ сгенерирован нейросетью и может содержать ошибки
Какой класс задач представляет умножение матриц
По сложности вычисления: O(n³) — Кубическая сложность
Классическое умножение матриц (naive algorithm):
def matrix_multiply(A, B):
"""
Умножить матрицы A (m x n) и B (n x p).
Результат: матрица размером (m x p)
Временная сложность: O(m * n * p)
В худшем случае (квадратные матрицы): O(n³)
"""
m, n = len(A), len(A[0])
n2, p = len(B), len(B[0])
# Три вложенных цикла → O(n³)
result = [[0] * p for _ in range(m)]
for i in range(m): # O(n) — строки A
for j in range(p): # O(n) — столбцы B
for k in range(n): # O(n) — внутреннее произведение
result[i][j] += A[i][k] * B[k][j]
return result
Анализ:
Для матриц размером n x n:
- 3 вложенных цикла
- Каждый цикл от 0 до n
- Операция: умножение + сложение
- Всего операций: n * n * n = n³
- Время: O(n³)
Классификация задачи
1. По вычислительной сложности
Кубическая сложность (O(n³))
Типичные задачи с O(n³):
- Умножение матриц (классическое)
- Floyd-Warshall алгоритм (все кратчайшие пути)
- LU разложение
- Determinant вычисление (наивный способ)
При n = 1000:
Операций: 10^9 (миллиард)
Время на современном ПК (~10^9 ops/sec): ~1 секунда
При n = 10000:
Операций: 10^12 (триллион)
Время: ~1000 секунд (17 минут!)
2. По характеру вычисления
Dense matrix computation (вычисление с плотными матрицами)
# Dense: большинство элементов ненулевые
A = [
[1, 2, 3],
[4, 5, 6],
[7, 8, 9]
] # 9 элементов, все используются
# Sparse: большинство элементов нулевые
B = [
[1, 0, 0],
[0, 2, 0],
[0, 0, 3]
] # 9 элементов, но только 3 ненулевых
# Для sparse матриц можно оптимизировать!
def sparse_multiply(A, B):
# Пропускаем нулевые элементы → намного быстрее
pass
Оптимизированные алгоритмы
1. Алгоритм Штрассена (Strassen) — O(n^2.807)
Идея: раздели матрицы на 4 блока, рекурсивно вычисли 7 вспомогательных матриц (вместо 8 умножений).
def strassen_multiply(A, B):
"""
Алгоритм Штрассена для умножения матриц.
Временная сложность: O(n^2.807) вместо O(n^3)
Для больших матриц (n > 1000) значительно быстрее!
"""
n = len(A)
# Base case: маленькие матрицы
if n <= 64: # Обычное умножение для маленьких матриц
return naive_multiply(A, B)
# Разделить на 4 блока
mid = n // 2
A11 = [row[:mid] for row in A[:mid]]
A12 = [row[mid:] for row in A[:mid]]
A21 = [row[:mid] for row in A[mid:]]
A22 = [row[mid:] for row in A[mid:]]
B11 = [row[:mid] for row in B[:mid]]
B12 = [row[mid:] for row in B[:mid]]
B21 = [row[:mid] for row in B[mid:]]
B22 = [row[mid:] for row in B[mid:]]
# Вычислить 7 матриц M1-M7 (вместо 8 умножений)
M1 = strassen_multiply(add(A11, A22), add(B11, B22))
M2 = strassen_multiply(add(A21, A22), B11)
M3 = strassen_multiply(A11, sub(B12, B22))
M4 = strassen_multiply(A22, sub(B21, B11))
M5 = strassen_multiply(add(A11, A12), B22)
M6 = strassen_multiply(sub(A21, A11), add(B11, B12))
M7 = strassen_multiply(add(A12, A22), sub(B21, B22))
# Скомбинировать результаты
C11 = add(sub(add(M1, M4), M5), M7)
C12 = add(M3, M5)
C21 = add(M2, M4)
C22 = add(sub(add(M1, M3), M2), M6)
# Объединить блоки
return combine_blocks(C11, C12, C21, C22)
Сложность Штрассена:
О(n^log₂7) = O(n^2.807)
Сравнение:
n = 1000:
Naive: 10^9 операций
Strassen: 10^8.5 операций (~3x быстрее)
n = 10000:
Naive: 10^12 операций
Strassen: 10^10.5 операций (~30x быстрее)
2. Алгоритмы Винограда и Coppersmith-Winograd
Coppersmith-Winograd: O(n^2.373)
Сложность: O(n^ω) где ω ≈ 2.373
Очень сложный для реализации, редко используется на практике
Потому что константа в Big O очень большая.
На практике: используй оптимизированные библиотеки
NumPy — самый быстрый вариант
import numpy as np
import time
# NumPy использует BLAS/LAPACK (написано на Fortran/C)
# Оптимизировано и распараллелено на уровне ОС
n = 1000
A = np.random.randn(n, n)
B = np.random.randn(n, n)
start = time.time()
C = A @ B # Или np.dot(A, B)
end = time.time()
print(f"Time: {end - start:.3f}s") # ~0.1 секунды (не 1000!)
# NumPy быстрее в 10000x раз! Почему?
# 1. Написано на C
# 2. Использует SIMD инструкции (SSE, AVX)
# 3. Многопоточность
# 4. Оптимальное использование кэша процессора
PyTorch для GPU
import torch
import time
# Если есть GPU, PyTorch использует CUDA
n = 10000
A = torch.randn(n, n, device='cuda')
B = torch.randn(n, n, device='cuda')
start = time.time()
C = torch.matmul(A, B) # На GPU
end = time.time()
print(f"Time on GPU: {end - start:.3f}s") # ~0.01 секунды
# На GPU это еще в 10x быстрее!
# GPU обрабатывает тысячи операций параллельно
Классификация по типу задачи
1. Linear Algebra / Numerical Computation
Умножение матриц входит в категорию:
- Linear algebra (линейная алгебра)
- Numerical computation (численные вычисления)
- Dense matrix operations (операции с плотными матрицами)
2. Parallel Computing — способна к распараллеливанию
# Матрица C[i][j] зависит только от строки i матрицы A
# и столбца j матрицы B
# → можно вычислять параллельно!
from multiprocessing import Pool
def compute_row(i):
return [sum(A[i][k] * B[k][j] for k in range(n)) for j in range(n)]
with Pool(4) as pool:
C = pool.map(compute_row, range(n)) # Распараллелить по строкам
3. Cache-heavy computation — зависит от кэша
Умножение матриц требует:
- Много операций (n³)
- На небольших данных (n² элементов)
→ Коэффициент compute-to-memory очень низкий
→ Критично использовать кэш процессора оптимально
Порядок вложенных циклов важен:
C[i][j] += A[i][k] * B[k][j]
↑ ↑ ↑
Column Row Row
Access (плохо) (хорошо)
Практические применения
1. Graphics (компьютерная графика)
- Трансформации координат (rotation, translation)
- 3D рендеринг
2. Machine Learning
- Forward/backward pass в neural networks
- Может быть 90% времени обучения!
3. Scientific computing
- Решение систем линейных уравнений
- Симуляции
4. Cryptography
- Некоторые криптографические алгоритмы
5. Signal processing
- Фильтрация и преобразования
Вывод
Умножение матриц — это:
✅ O(n³) задача (кубическая сложность в классическом варианте)
✅ Numerical computation (численные вычисления)
✅ Параллелизуемая (хорошо распараллеливается)
✅ Cache-sensitive (результат зависит от кэша)
✅ Фундаментальная операция (в линейной алгебре и ML)
На практике:
- Используй NumPy/PyTorch, не реализуй сам
- NumPy оптимизирует порядок циклов и использует BLAS
- Для GPU используй CUDA/cuBLAS
- Если нужны огромные матрицы → используй разреженные матрицы и специальные алгоритмы