dist（）の複雑さは何ですか？

Question

私はdistの機能をRで使いました。私はその時間の複雑さを疑問視しています。

私は、階層的クラスタリングが時間複雑さがN^2*logNであることを知っています。そして、階層的クラスタリングは、階層的クラスタリングを適用する前に、距離行列が必要であることをRの中で以下のように2つの部分から構成されている。私はこれがN^2の複雑さを取ると思いますか？マトリックスXがN行P列を有する場合

Answer 1

正確に、dist(X)の複雑さは3N(N-1)P/2あります。これはN(N - 1)/2 * 3Pによって計算されます。

説明：

• 得られた距離行列内のN(N - 1)/2エントリがあります。
• 各エントリは、Pベクトル（プラス平方根）の間のドット積であり、それぞれがPの減算、Pの乗算、およびPの加算を含みます。