ベクトル化は複雑さを変化させますか？

Question

私は複雑さO（n^3）でMATLABにコードを書いた。ループの1つを削除し、代わりにベクトル化されたフォームを使用しました。その結果、実行時間が減少しました。私はベクトル化が一般的に性能を向上させることを理解しています。私がよく分からないことは、ベクトル化が複雑さを変えないと仮定したことです。

次のように私はいくつかの実験をしました：

私は（私は8倍程度によって期待される）2倍2.5倍程度増加し、実行時間を入力サイズを増加させたとき。

私は最初の仮定（ベクトル化が複雑さを変えない）が有効かどうかはわかりません。誰にも洞察がありますか？

ありがとうございます。

Answer 1

私は非常に一般的な方法では、実際にはスループット（待ち時間）と操作の数（複雑さ）の違いだと思います。アルゴリズムのための非常に専用のASICを構築する場合は、n^3回の演算を行う必要があります。ベクトル化することによって、これらの操作のいくつかは互いに独立して並行して実行できるということです。 Matlabと現在のプロセッサーはもっと巧妙で、特定の操作を '並列'で行うことができます。 64ビットプロセッサは2-32bit和を行うことができ4-16bitなど

各操作を行わなければならない2つのOの両方のアルゴリズム（N^3）、のだと思う完全に独立して（あなたはこのアルゴリズムをベクトル化することができます）と、 bもう1つはシリーズでなければなりません（ベクトル化できません）。それらのそれぞれのための特別なハードウェアはどちらもn^3操作を必要とします。しかし、のハードウェア/ゲートをにすると、1クロックサイクルで処理を完了することができます。bハードウェア/ゲートの数が増えれば、タスクはn^3クロックサイクルかかるでしょう。

---

EDIT：ベクトル化の速度を説明する

いくつかのコード、複雑（#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; 

を増加させないだろうが、今は技術的にMathWorks社のMATLABなどの操作ごとにいくつかの余分なオーバーヘッドを持っています操作が意味をなすかどうかをチェックして、ループの速度を大幅に遅くします。しかし、これは一般的に傾向を説明するための一例に過ぎません。