質問があります。
理論的なコンピューター サイエンスの観点から、アルゴリズムを分析するときに、アルゴリズムが新しいデータ構造を初期化する場合、そのデータ構造を空間の複雑さの一部と見なします。
今、私はこの部分についてあまり確信が持てません。
の配列を持っていて、ポインターintのマップを使用してそれらをマップしたいとしましょう。intそのような
std::map<int*,int*> mymap;
for (int i = 1; i < arraySize; i++) {
mymap[&arr[i-1]]=&arr[i];
}
このアルゴリズムがポインターを使用していない場合、サイズ n でマップを初期化していることを明確に述べることができます。したがって、スペースの複雑さは O(n) ですが、ポインターを使用しているこの場合、スペースの複雑さはどうなるでしょうか。このアルゴリズムの？