矢量化会改变复杂性吗？

Question

我用MATLAB写了一段复杂度为O(n^3)的代码。我删除了其中一个循环并改用矢量化形式。结果运行时间减少了。我一般理解矢量化可以提高性能。我不确定的是我假设矢量化不会改变复杂性。

我做了如下实验：

当我将输入大小增加 2 倍时，运行时间增加了大约 2.5 倍（我预计大约是 8 倍）。

现在我不确定我最初的假设（矢量化不会改变复杂性。）是否有效。有没有人有见识？

谢谢。

Answer 1

以非常一般的方式，我认为差异实际上是吞吐量（延迟）与操作数（复杂性）。如果你要为你的算法构建一个非常专用的 ASIC，你将不得不进行 n^3 次操作。通过矢量化，您是说其中一些操作可以彼此独立地并行执行。 Matlab 和当前的处理器更聪明，可以在 'parallel' 中执行某些操作，例如64 位处理器可以进行 2-32 位求和 4-16 位等

考虑 O(n^3) 中的两种算法，a 其中每个操作必须完全独立完成（您可以向量化此算法）和 b 另一个它们必须是系列（你不能向量化它）。其中每一个的特殊硬件都需要 n^3 操作。但是，通过为 a 使用 more hardware/gates，您可以在 1 个时钟周期内完成任务，而对于 b more hardware/gates 对你没有帮助，任务将花费 n^3 个时钟周期。

编辑：

一些代码来说明矢量化速度，虽然复杂度（#operation）不会增加

clear variable;

Iterations = 100;
n = 2^20;
a = randi(100,[1,n]);
b = randi(100,[1,n]);

profile on;
for loop=1:Iterations
    % Full vector approach
    vector = a*b.';

    % Partial vector approach
    vector2 = sum(a.*b);

    % Direct mathematical approach
    serial = 0;
    for id=1:n
        serial = serial + a(id)*b(id);
    end
end
profile viewer;

现在从技术上讲，matlab 每个操作都有一些额外的开销，比如检查操作是否有意义等，从而显着减慢 for 循环。但总的来说，这只是一个说明趋势的例子。

矢量化会改变复杂性吗？

Does vectorization change the complexity?

complexity-theory

matlab

matrix

vectorization