Экспериментально определения вычислительной сложности матрицы определителя

Question

мне нужна помощь в определении экспериментально вычислительной сложности определителя матрицы пхпа

Моего код:

import numpy as np 
    import timeit 
    t0 = time.time() 
    for n in range(1, 10): 
     A = np.random.rand(n, n) 
     det = np.linalg.slogdet(A) 
     t = timeit.timeit(lambda: det) 
     print(t) 

Но я получаю то же время для каждого п, следовательно, , вычислительная сложность: O (N), которая неверна, поскольку она должна быть O (N^3). Любая помощь приветствуется.

Answer 1

Для чего он стоит, любой значащий бенчмаркинг обычно требует достаточно большого N, чтобы дать компьютеру что-то пережевывать. Матрица 10x10 не достаточно велика, чтобы начать видеть сложность. Начните бросать цифры, такие как 100, 1000, 10000 и т. Д., Тогда вы увидите свое масштабирование.

Например, если я немного изменить код

for n in range(1, 14): 
    t0 = time.time() 
    p = 2**n 
    A = np.random.rand(p,p) 
    det = np.linalg.slogdet(A) 
    print('N={:04d} : {:.2e}s'.format(p, time.time() - t0)) 

Это приводит к

N=0002 : 4.35e-02s 
N=0004 : 0.00e+00s 
N=0008 : 0.00e+00s 
N=0016 : 5.02e-04s 
N=0032 : 0.00e+00s 
N=0064 : 5.02e-04s 
N=0128 : 5.01e-04s 
N=0256 : 1.50e-03s 
N=0512 : 8.00e-03s 
N=1024 : 3.95e-02s 
N=2048 : 2.05e-01s 
N=4096 : 1.01e+00s 
N=8192 : 7.14e+00s 

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