algorithm - O(n) 時間で正方行列を追加しますか?

Question

nと という名前の同じサイズの 2 つの正方行列があるAとしBます。

AとBは、主対角線の各エントリが同じ値 (つまりA[0,0] = A[1,1] = A[2,2] ... = A[n,n]とB[0,0] = B[1,1] = B[2,2] ... = B[n,n]) であるというプロパティを共有します。

O(n^2) ではなく、O(n) 時間で相互に加算できるようにAandを表現する方法はありますか?B

Answer 1

一般：いいえ。

nxn行列の場合、入力する出力n^2値があります。それには時間がかかりますO(n^2)。

あなたの場合：いいえ。

O(n)入力/出力値が依存していても、独立したままですO(n^2)。したがって、以下の全体的な実行時間を短縮できる表現はありませんO(n^2)。

しかし...

ランタイムを短縮するには、従属値の数を に増やす必要があります (必ずしも十分ではありません) O(n^2)。明らかに、これが可能かどうかは、特定のシナリオによって決まります...

Answer 2

Oli Cherlesworth の回答を補完するために、疎行列 の特定のケースでは、多くの場合、 のランタイムを取得できることを指摘したいと思いますO(n)。

たとえば、行列が対角であることがわかっている場合、結果の行列が対角になることもわかっているため、値を計算するだけで済みnます。同様に、 で追加できるバンド マトリックスとO(n)、より「ランダムな」スパース マトリックスがあります。一般に、スパース行列では、行ごとの非ゼロ要素の数は多かれ少なかれ一定です (これらの要素は、たとえば有限要素計算から、またはグラフ隣接行列などから取得します)。 「圧縮された行ストレージ」または「圧縮された列ストレージ」などの適切な表現でO(n)は、2 つの行列を追加する操作を使用することになります。

また、ランダムエラーまで、実際のソリューションから「それほど遠くない」最終値を知ることのみを提案するサブリニアランダム化アルゴリズムについても特筆します。