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

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, чтобы дать компьютеру что-то, что можно пережевать. Матрица 10х10 недостаточно велика, чтобы начать видеть сложность. Начните бросать числа, такие как 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 расти, вы можете начать видеть масштабирование.

Answer 2

Есть несколько возможных причин:

1. Компьютер, используемый для генерации этих чисел, был занят чем-то другим, когда выполнялись «медленные» операции, такие как n = 2 или n=16 операций.
2. особенно для n=2, возможно, некоторое кеширование было выполнено после первого цикла, что ускорило последующие запуски.

Вы также обычно ожидаете, что n=1 будет иметь худшее отношение времени работы к n просто из-за постоянных накладных расходов, таких как инициализация переменной.