以大O表示的时间复杂性
以大O表示的时间复杂性
提问于 2020-01-30 16:07:50
我有一个代码，可以对图像进行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现在涉及到的基本操作是使用SVD。所以我的问题是，大O符号的时间复杂度是否应该与矩阵的正常奇异值分解相同？如果不是，我们应该考虑哪些项，以确定图像输入大小的复杂性？重塑元素是否也考虑了时间复杂性，或者它只是O(1)？有人能帮帮忙吗？
回答 1
Stack Overflow用户
回答已采纳
发布于 2020-01-30 16:57:46
首先，固定大小的reshape (在循环内)的复杂度是O(1)。因此，for循环的复杂性是\Theta(m*n)。其次，svd的复杂性是O(max(m, n) * min(m, n))，根据函数将返回什么数据，它可以是O(max(m, n)^2) (根据this reference)。此外，根据@Daniel注释，在代码末尾进行重塑的最坏情况是可以O(m*n) (通常小于这个值)。
因此，代码的复杂性是O(max(m, n)^2)。此外，由于循环的原因，它是Omega(m*n)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/59981489
复制相关文章
相似问题
腾讯云开发者
