Применяется ли временная сложность умножения матриц только к большим N?
Временная сложность умножения (квадратных, наивных) матриц равна O(N3), например этот ответ
Я могу запустить быстрый скрипт
import numpy as np
import time
import matplotlib.pyplot as plt
def time_matmul_n(n):
#Create two arrays of dimension n
arr1 = np.random.rand(n, n)
arr2 = np.random.rand(n, n)
t0=time.process_time_ns() #start the clock
np.matmul(arr1,arr2)
t1=time.process_time_ns()
return t1-t0
N = 100
n_values = range(N)
t_values = np.zeros_like(n_values)
for i,n in enumerate(n_values):
t_values[i] = time_matmul_n(n)
#Plot the results
plt.plot(n_values,t_values)
Это дает мне что-то вроде
Я понимаю, что здесь много шума, и время выполнения будет варьироваться в зависимости от процессов, происходящих на моем ноутбуке, но это не похоже на масштабирование вроде O(N3).
Я явно чего-то не понимаю. Может ли кто-нибудь объяснить, почему график не выглядит O(N3)-подобным? Имеет ли это значение только тогда, когда N становится большим?
Вероятно, было бы гораздо очевиднее, если бы вы выбрали размеры, увеличивающиеся каждый раз в 2 раза. Вам также необходимо использовать оптимизирующий компилятор и тестировать что-то, что занимает как минимум секунду или две для запуска, иначе шум переключения задач ОС перебьет ваш сигнал. Вы должны увидеть, что шаги происходят в тот момент, когда каждый уровень кэша исчерпывается по мере увеличения N. Кстати, в каких единицах времени находится ваша ось Y?
Ответы 2
Может ли кто-нибудь объяснить, почему график не выглядит O(N3). Имеет ли это значение только тогда, когда N становится большим?
Есть несколько причин:
Временная сложность связана с асимптотическим поведением. По определению это станет очевидным только для значений N, которые больше некоторого минимального значения, которое необходимо определить.
Для слишком маленьких размеров этот процесс тривиален и занимает всего миллисекунду или меньше, так что ваши измерения времени в большей степени определяются другими накладными расходами.
Связано: увеличение размера ввода с шагом 1 ограничивает диапазон N, для которого вы визуализируете результат. Вы можете улучшить это, взяв большие (но постоянные) приращения для N.
Поскольку случайные входные данные могут даже давать разные результаты для одного и того же значения N, ожидается, что вы получите ошибочные результаты. Чтобы улучшить это, повторите операцию для нескольких случайных входных данных с одинаковым N, а затем возьмите среднее значение затраченного времени.
Вот как можно изменить ваш сценарий, чтобы получить более убедительные результаты:
import numpy as np
import time
import matplotlib.pyplot as plt
def time_matmul_n(n):
acc = 0
for i in range(10): # Multiple times to take average
arr1 = np.random.rand(n, n)
arr2 = np.random.rand(n, n)
t0 = time.process_time_ns()
np.matmul(arr1, arr2)
t1 = time.process_time_ns()
acc += t1-t0
return acc / 10
# Larger sizes, increase with steps
N = 1500
step = 50
n_values = range(step, N, step)
t_values = np.zeros_like(n_values)
# This takes a while to run
for i,n in enumerate(n_values):
t_values[i] = time_matmul_n(n)
print(i, t_values[i]) # Give some indication of progress
# Plot the results
plt.plot(n_values,t_values)
Теперь вы получите график, который выглядит примерно так:
С N=1000 вы получите лучшие результаты, так как:
С N=1500:
Временная сложность всегда связана с большим N, фактически с асимптотическим поведением.