4

我需要帮助通过实验确定矩阵 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)。任何帮助将非常感激。

4

2 回答 2

2

对于它的价值，任何有意义的基准测试通常都需要足够大的 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增长，您可以开始看到缩放。

于 2016-11-19T00:31:34.263 回答
0

有一些可能的原因：

  1. 当 n=2 或 n=16 等“慢”操作完成时，用于生成这些数字的计算机正忙于做其他事情
  2. 特别是对于 n=2，可能在第一个循环之后完成了一些缓存，从而加快了后续运行。

您通常还期望 n=1 具有最差的运行时间与 n 的比率，这仅仅是因为变量初始化等恒定开销。

于 2021-05-09T22:36:34.723 回答