ベクトル化は演算の回数を変えず、作業領域を変える

$X$ を $n\times d$ の配列（$n$ 個の点の座標）とし、全対の距離の 2 乗 $D_{ij}=\sum_{k=1}^d(X_{ik}-X_{jk})^2$ を次の 3 通りで計算する。

• (a) 二重ループ: $i,j$ についてのループの中で、$k=1,\ldots,d$ について差・2 乗・足し込みをスカラーで行う。
• (b) ブロードキャスト: ((X[:, None, :] - X[None, :, :]) ** 2).sum(axis=2)。
• (b′) ブロック化: 行を $b$ 個ずつ（$1\le b\le n$）に分け、各ブロック X[s:s+b] について (b) と同じ式を計算する。

このとき、

1. 3 通りとも、引き算を $n^2d$ 回、乗算を $n^2d$ 回、足し算を $n^2(d-1)$ 回行う。RAM モデルでの計算時間はどれも $\Theta(n^2d)$ である。
2. 入力と出力 $D$ のほかに使う作業領域は、(a) が $O(1)$、(b) が $n^2d$ 要素の一時配列、(b′) が高々 $bnd$ 要素の一時配列である。