Блог

Главная - Вопросы по программированию - Временная сложность scipy.null_space()

Временная сложность scipy.null_space()

#python #numpy #scipy #time-complexity #big-o

Вопрос:

У меня есть следующий фрагмент кода:

 (... some previous code ...)

vecs = np.array(vecs_list, dtype=int)

kernel = scipy.linalg.null_space(np.transpose(vecs))
rows, columns = kernel.shape

(... some ensuing code ...)

Позвольте мне прояснить некоторые вещи:

  • vecs_list : представляет собой список из L списков, каждый из которых имеет размер s. Мне нравится думать об этом как о матрице L x s.
  • есть причина, по которой я начинаю со списка, а затем преобразую его в np.массив (это связано с характером предыдущего кода, но объект, с которого мы начинаем, действительно должен быть списком списков!).


Мой вопрос заключается в следующем: какова временная сложность этого фрагмента кода в его нынешнем виде?

На мой взгляд, ответ звучит примерно так:

  • vecs = np.array(vecs_list, dtype=int) : может занять O(s**L)* времени
  • np.transpose(vecs) : O(1) время
  • scipy.linalg.null_space(*) : использует SVD, но я не совсем уверен, что это означает для сложности времени. Я полагаю, что я ожидал бы O(n^3) для матрицы n x n, но здесь матрица не является квадратной матрицей, и я не уверен в последствиях. Знаете ли вы, какова временная сложность этого метода? Есть ли лучшая альтернатива с точки зрения big-O?
  • kernel.shape : O(1) время

Заранее спасибо.

РЕДАКТИРОВАТЬ: После нескольких быстрых исследований, в которых я варьировал s и L отдельно, я получил следующие графики: введите описание изображения здесь

введите описание изображения здесь

что, по-видимому, предполагает, что O(s^2 L^2). Это немного беспокоит, потому что это указывает на то, что если s=L, то O(s^4) вместо O(s^3), как можно было бы ожидать. Есть какие-нибудь мысли по этому поводу? Спасибо!

Комментарии:

1. Вам действительно нужны kernel или вам просто нужны его размеры?

2. Проверьте это: math.stackexchange.com/questions/649587/…

3. Мне это kernel понадобится ниже в коде (помимо размеров, конечно).

4. Я проверил эту ссылку. Две проблемы: (1) в нем обсуждаются только квадратные матрицы n на n (что не обязательно в моем случае), (2) в нем конкретно не обсуждается реализация scipy.linalg.null_space. Я хочу убедиться в сложности этого конкретного метода scipy.

5. примерно каковы размеры (l,s)?

Метки: