algorithm - アルゴリズムのスペース効率

Question

アルゴリズムの教科書のどれもスペース効率についてあまり言及していないように思われるので、一定のメモリのみを必要とするアルゴリズムを求める質問に出くわしたとき、私は本当に理解していません。

コンスタントメモリを使用するアルゴリズムとコンスタントメモリを使用しないアルゴリズムのいくつかの例の例は何でしょうか？

Answer 1

アルゴリズムの場合：

a）Nに依存する、または

b）Nに依存する量のメモリを割り当てます

それからそれは一定の記憶ではありません。それ以外の場合は、おそらく次のようになります。入力のサイズ/値に関係なく、アルゴリズムが使用するメモリの量に一定の上限がある場合、正式には定数メモリです。入力が占めるメモリは含まれていないため、明確にするために、一定の「余分な」メモリについて話すことがあります。

したがって、Cで整数の配列の最大値を見つけるための定数メモリアルゴリズムは次のとおりです。

int max(int *start, int *end) {
    int result = INT_MIN;
    while (start != end) {
        if (*start > result) result = *start;
        ++start;
    }
    return result;
}

これは、入力配列の要素数に比例するスタックスペースを使用するため、非定数メモリアルゴリズムです。ただし、コンパイラが非再帰的な同等物に最適化できる場合は、定数メモリになる可能性があります（Cコンパイラは、末尾呼び出しの最適化を除いて、通常は気にしません。ここでは機能しません。 ）：：

int max(int *start, int *end) {
    if (start == end) return INT_MIN;
    int tail = max(start+1, end);
    return (*start > tail) ? *start : tail;
}

これが定空間ソートアルゴリズム（今回はC ++）で、これはO（N！）時間かそこら（多分O（N * N！））です：

void sort(int *start, int *end) {
    while (std::next_permutation(start,end));
}

これがO（N）空間ソートアルゴリズムです。これはO（N ^ 2）時間です。

void sort(int *start, int *end) {
    std::vector<int> work;
    for (int *current = start; current != end; ++current) {
        work.insert(
            std::upper_bound(work.begin(), work.end(), *current),
            *current
        );
    }
    std::copy(work.begin(), work.end(), start);
}

Answer 2

非常に簡単な例：文字列内の文字数を数える。反復することができます：

int length( const char* str )
{
    int count = 0;
    while( *str != 0 ) {
       str++;
       count++
    }
    return count;
}

または再帰的：

int length( const char* str )
{
    if( *str == 0 ) {
        return 0;
    }
    return 1 + length( str + 1 );
}

最初のバリアントは、文字列の長さに関係なく、いくつかのローカル変数のみを使用します。スペースの複雑さはO(1)です。2番目の再帰を削除せずに実行する場合は、各深度レベルに対応するリターンアドレスとローカル変数を格納するための個別のスタックフレームが必要です。スペースの複雑さはO(n)、n文字列の長さです。

Answer 3

たとえば、配列の並べ替えアルゴリズムを考えてみましょう。ソートされた要素を ( Θ ( n ))に入れる元の配列と同じ長さの新しい配列を使用できます。または、配列をその場でソートし、2 つの要素を交換するために追加の一時変数を 1 つ使用するだけです ( Θ (1))。