algorithm - 2次元行列を初期化する時間計算量はどれくらいですか？

Question

行列をすべて0の値に初期化したいと思います。複雑さはO（1）またはO（n）ですか？

Answer 1

実際、初期化の複雑さが問題であり、さらにマトリックスアクセスが注文された場合は、次のことができます。

1. マトリックス要素（行または列、さらにはセル）が初期化されたものを追跡するための追加のデータ構造があります。
2. 要素にアクセスするときにのみ、要素を遅延初期化します。

このアプローチでは、マトリックスの初期化において、以降の処理よりも複雑になることはありません。

Answer 2

それはの意味に依存しますN

• Nが正方行列の行と列の数である場合、複雑さは次のようになります。O(N^2)
• Nが行列内の要素の総数である場合（つまり、N = R*Cは行R数、Cは列数）、複雑さはO(N)です。