Experimentell Bestimmung Komplexität der Matrix Rechen Determinante

Question

ich helfen experimentell die Rechenkomplexität der Determinante einer Matrix nxn

Mein Code zu bestimmen müssen:

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) 

Aber ich bekomme die gleiche Zeit für alle n, daher , Komplexität der Berechnung: O (N), was nicht korrekt ist, da es O (N^3) sein soll. Jede Hilfe würde sehr geschätzt werden.

Answer 1

Für das, was es wert ist, erfordert jedes aussagekräftige Benchmarking typischerweise ausreichend große N, um dem Computer etwas zum Kauen zu geben. Eine 10x10-Matrix ist nicht annähernd groß genug, um Komplexität zu erkennen. Beginnen Sie, Zahlen wie 100, 1000, 10000 usw. zu werfen, dann sehen Sie Ihre Skalierung.

Zum Beispiel, wenn ich Ihren Code

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)) 

Dies führt zu

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 

Sie, dass für sehr kleine Werte von N sehen können, einige kleine Wert Optimierungen und Tricks leicht ändern machen es schwer, zu sehen O() Komplexität, aber wie die Werte von N wachsen, können Sie beginnen, die Skalierung zu sehen.