c - ゼロで埋められた配列を初期化するランタイム

Question

スタックでゼロ フィル初期化構文を使用して次の配列を定義するとします。

int arr[ 10 ] = { 0 };

... 実行時間は一定ですか、それとも線形ですか?

私の仮定は、それが線形実行時間であるということです。私の仮定は、callocゼロを埋めるためにすべてのバイトを通過しなければならないという事実のみを対象としています。

注文 xxx だけでなく、その理由も教えていただければ、すばらしいことです。

Answer 1

実行時間は配列サイズに比例します。

その理由を理解するために、配列を任意の値に初期化する memsetのサンプル実装を次に示します。アセンブリ言語レベルでは、これはコードで行われていることと同じです。

void *memset(void *dst, int val, size_t count) {
    unsigned char *start = dst;
    for (size_t i = 0; i < count; i++)
        *start++ = value;
    return dst;
}

もちろん、コンパイラは組み込み関数を使用して一度に複数の配列要素を設定することがよくあります。配列のサイズとアラインメントやパディングなどによっては、ベクトルの長さに基づくステップ サイズで、配列の長さ全体のランタイムが階段のようになる可能性があります。配列サイズのわずかな違いで、これにより実質的にランタイムが一定になりますが、一般的なパターンは依然として線形です。

Answer 2

これは、実際には氷山の質問のヒントです。あなたが本当に求めているのは、配列を初期化する順序 (Big Oh) です。基本的に、コードは配列の各要素をループし、それらをゼロに設定しています。for ループを記述して同じことを行うことができます。

そのループの大きさのオーダーは O(n) です。つまり、ループに費やされる時間は、初期化される要素の数に比例して増加します。

ハードウェアが位置 X から Y までのすべてのバイトをゼロに設定する命令をサポートし、その命令が M 命令サイクルで機能し、バイト数がゼロに設定されているにもかかわらず M が変更されない場合、それは次数 k になります。または O(k)。

一般に、O(k) はおそらく一定時間、O(n) は線形と呼ばれます。