Сложность времени с точки зрения Big O - PullRequest
Новая
       37

Сложность времени с точки зрения Big O

1 голос
/ 30 января 2020

У меня есть код, который выполняет 4-уровневую декомпозицию изображения. Уровни аналогичны вейвлет-преобразованию изображения, которое разбивает изображение на 4 уровня: аппроксимирующая часть и три подробные части. Код, который я реализовал, использует обобщенный SVD для этой декомпозиции. Вот код 

      function[Y,U] = MSVD1(X)
       %multiresolution SVD (MSVD)
        %input-> x: image (spatial domain)
        %outputs-> Y: one level MSVD decomposition of x
        %          U: the unitary matrix (U in SVD)
         [m,n] = size(X);
        m = m/2; n = n/2;
        A = zeros(4,m*n); 
        for j = 1:n
         for i = 1:m
           A(:,i + (j-1)*m) = reshape(X((i-1)*2+(1:2),(j-1)*2+(1:2)),4,1);
         end
        end
      [U,S] = svd(A);
       T = U'*A;
      Y.LL = reshape(T(1,:),m,n);
      Y.LH = reshape(T(2,:),m,n);
      Y.HL = reshape(T(3,:),m,n);
      Y.HH = reshape(T(4,:),m,n);
      end

Теперь основные операции c, используемые для этого, используют SVD. Поэтому мой вопрос заключается в том, должна ли временная сложность в терминах обозначения Big O быть такой же, как у обычного SVD матрицы? Если нет, то какими должны быть условия, которые нам необходимо учитывать, чтобы найти сложность с точки зрения размера входного изображения? Добавляет ли изменяющиеся элементы также учет сложности времени или это просто O (1)? Может кто-нибудь помочь?

1 Ответ

3 голосов
/ 30 января 2020

Во-первых, сложность постоянного размера reshape (внутри l oop) равна O(1). Следовательно, сложность for l oop равна \Theta(m*n). Во-вторых, сложность svd равна O(max(m, n) * min(m, n)), и в зависимости от того, какие данные будут возвращены функцией, она может быть O(max(m, n)^2) (согласно эта ссылка ). Более того, основываясь на комментарии @Daniel, наихудший сценарий изменения формы в конце вашего кода может O(m*n) (обычно это меньше).

Следовательно, сложность кода O(max(m, n)^2). Кроме того, из-за l oop это Omega(m*n).

...