Как рассчитать временную сложность заданного алгоритма (гребень регрессии)? - PullRequest
Новая
       14

Как рассчитать временную сложность заданного алгоритма (гребень регрессии)?

1 голос
/ 06 июня 2019

У меня есть следующее выражение, и мне нужно рассчитать временную сложность этого алгоритма.Может ли кто-нибудь помочь получить правильную временную сложность этого алгоритма. 

% save a matrix-vector multiply
Atb = A'*b;

% cache the factorization (using cholesky factorization)
[L U] = factor(A, a);  

for( k = 0; k < maxiter; k++) 
    {
         x^k+1 = (A^TA + a* I)^-1 (A^Tb + a (z^k - u^k))^T
    }

Где A = матрица mxn и n >>> m, b, u, z = nx1 векторов, I = единичная матрица и a = 0,001

1 Ответ

0 голосов
/ 06 июня 2019

Наиболее интенсивная вычислительная операция здесь - это инверсия матрицы, поэтому она зависит от того, как вы реализуете эту операцию. Если мы предположим, что вы реализовали с помощью алгоритма Гаусса-Джордана, который занимает O(n^3), то общая сложность составляет O(maxiter * n^3). Здесь я принимаю во внимание, что n больше m (A^T*A занимает O(m*n^2)).

Если вы вычислите (A^T*A + a*I)^-1 и A^Tb снаружи, то у вас останется 

Inv * (Atb + a(z^k - u^k))^T

, то есть O(n^2), потому что вам нужно умножить матрицу nxn на вектор nx1, в то время как сложение и вычитание принимают O(n).

Тем не менее, у вас есть некоторые несоответствия в размерах, которые я описал в комментариях к вопросу.

...