これは一般的な質問であり、C、C ++、Javaなどの特定の言語に適用できます。
どのように実装しても、2つのループを使用するよりも効率的になることはできません。これによりn^2の効率が得られます。 。
for(i=0;i<n;i++)
for(j=0;j<n;j++)
a[i][j]=1;
最近のインタビューでこれを聞いたのですが、これ以上効率的なものは考えられませんでした。インタビュアーから得たのは、再帰を使用するか、2D配列をリンクリストに変換して、n^2よりも効率的にすることができるということだけでした。これが可能かどうかは誰にも分かりますが、可能であればどのようにしたらよいでしょうか。少なくとも理論的には、実際的ではないにしても。
編集：実際の質問では、2つのセルの座標がわかります。たとえば、5x5の行列があり、2つの座標が（2,0）と（ 3,3）、私は記入する必要があります：
（2,0）（2,1）（2,2）（2,3）（3,0）（3,1）（3,2）（3、 3）
残りのセルをそのままにしておきます。
それはあなたが何を意味するかに依存します。質問が単純な配列、つまり一連の連続したメモリ位置に関するものであり、初期化の場合、この「行列」のすべてのメモリ位置に値を入れることを意味する場合、答えはノーであり、O（n * m）よりも優れていることは不可能です。私たちはそれを証明することができます：
アルゴリズムfill(A[n][m], init_val)が正しい（つまり、のすべてのメモリ位置を埋めるA）複雑さが（の一部ではないことを意味する）g(n,m)よりも小さいと仮定すると、十分な大きさの場合、=メモリ位置の数になります。メモリ位置を埋めるには1つの操作が必要なため、アルゴリズムはほとんどの場所を埋めることができます[ハードウェアが組み合わせ操作を提供する場合を除いて、少なくとも別のメモリ位置を「選択」する操作も実行する必要があるため、実際には半分です]。、これはアルゴリズムが正しくないことを意味します。O(n*m)g(n,m)Ω(n*m)nmg(n,m) < n*mfillg(n,m)n*mfill
メモリの場所を埋めるのに一定の時間がかかる場合も同じことが当てはまります。より大きな値をk選択するだけです。nm
他のすでに提案されているように、O(n^2)初期化時間を回避するために他のデータ構造を使用できます。amitの提案では、ある種の遅延評価を使用します。これにより、配列をまったく初期化せず、要素にアクセスするときにのみ初期化できます。
これにより、Ω(n^2)最初はコストが削減されますが、配列の要素にアクセスするにはより複雑な操作が必要になり、さらに多くのメモリが必要になることに注意してください。
インタビュアーが何を意味するのかは明確ではありません。配列をリンクリストに変換するには時間が必要Ω(L)です（Lは配列の長さ）。したがって、行列全体をリンクリストに変換するには、Ω(n^2)時間と実際の初期化が必要になります。再帰を使用してもまったく役に立ちません。そのような再帰がT(n) = 2T(n/2) + O(1)発生するだけで、漸近的な複雑さのメリットはありません。
原則として、すべてのアルゴリズムは、事前に何らかの形式の知識を持っている場合を除いて、少なくともすべての入力をスキャンする必要があります（たとえば、要素がソートされます）。あなたの場合、スキャンするスペースはΘ(n^2)であり、したがって、それを埋めたいすべてのアルゴリズムは少なくともである必要がありますΩ(n^2)。この複雑さよりも小さいものは、何らかの仮定を行うか（たとえば、メモリにデフォルトで初期化値が含まれている-> O(1)）、または別の問題を解決します（たとえば、遅延配列やその他のデータ構造を使用します）。
で配列を初期化できますが、O(1)3倍のスペースを消費し、マトリックス内の要素アクセスごとに余分な「作業」を消費します。
実際には、行列はメモリ内の1D配列であるため、同じ原則が引き続き当てはまります。
このページでは、その方法について詳しく説明しています。
2次元配列を同じ要素で埋める場合、実際にすべての要素を埋めるのであれば 、少なくともn ^ 2回の操作を行う必要があります（2次元配列がn * nの場合）。
複雑さを軽減する唯一の方法は、並列プログラミング手法を使用することです。たとえば、n個のプロセッサが与えられた場合、最初の入力には配列の最初の行が割り当てられます。これはn個の演算です。次に、各プロセッサPiは、k=0からn-1の場合に行kのarray[i]を行k+1のarray[i]に割り当てます。n個のプロセッサが並列に動作しているため、これもO（n）になります。
このアプローチを本当に実装したい場合は、OpenMPIやmpichなどの無料の並列プログラミング環境を探すことができます。