實驗測定計算矩陣的複雜性決定

Question

我需要幫助確定實驗矩陣的行列式的計算複雜度爲n×n

我的代碼：

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) 

但我得到同樣的時間對於每個n，因此，計算複雜度：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的值增長，您可以開始看到縮放。