c++ - 配列の初期化の時間の複雑さは?

Question

C または C++ での配列初期化の次の 2 つのケースを検討してください。

ケース 1:

int array[10000] = {0}; // All values = 0

ケース 2:

int array[10000];
for (int i = 0; i < 10000; i++) {
    array[i] = 0;
}

両方とも同じ時間がかかりますか？ケース 1 の複雑さは? で、どっちがいい？

Answer 1

配列が静的な期間 (グローバル変数) である場合、コードを必要としないため、最初のものがはるかに好ましいと言えます。ランタイム環境によって初期化されます。

変数が自動継続時間 (ローカル変数) の場合、どちらが優れているかはコンパイラによって異なります。ほとんどの場合、どちらも非常に似ています。

自動保存期間変数の複雑さは、すべての場合で O(n) です。最初のケースは、静的ストレージ期間変数の O(1) です。

もちろん、配列に値 5 を入力したい場合は5、ソース ファイルに 10000 を書き込む必要がないため、2 番目のオプションの方がはるかに優れています。

memset(array, 0, sizeof(array));また、コンパイラによっては、両方を使用するよりも使用する方がよい場合もあります。memsetこれはまだ O(n) ですが、ループの場合にコンパイラが生成するもの [および初期化された変数に対して行うもの] よりも最適化されている可能性があるため、配列を埋めるのにかかる実際の時間は短くなる可能性があります。memset配列を埋めるためには機能しません5。

すべての配列に値 5 を設定するために使用することもできstd::fill(array, &array[10000], 5);、コンパイラはそれを最適化する適切な仕事をするはずです。

最後に、これらの種類のことは、頻繁に実行されるコードで実行している場合にのみ問題になることを指摘しておく必要があります。40KB のデータを埋めるのに十分な時間がかかり、それ自体が本当に心配になるのは久しぶりです。20年以上のようです。