矩阵决定元计算复杂度的实验测定

Question

我需要帮助来实验确定矩阵nxn的行列式的计算复杂性

我的代码：

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

这导致

^{pr2}$

您可以看到，对于非常小的N值，一些小值优化和技巧使您很难看到O()的复杂性，但是随着N值的增长，您可以开始看到缩放。在