In-placeアルゴリズム
計算複雑性理論では、in-place アルゴリズムは空間複雑性が O(1) であるアルゴリズム(DSPACE(1)クラス)を全て含む。このクラスは非常に限定されており、正規言語と等価である。実際、上述の例にあるアルゴリズムはいずれもこのクラスには含まれない。
このため、一般に in-placeアルゴリズムにはLクラスのアルゴリズム(すなわち、O(log n)の追加領域を必要とする問題のクラス)を含める。これは、定義と矛盾しているように見えるが、抽象世界では非常に巨大な入力を考慮する。実際のコンピュータでは、物理メモリ量が限られているためポインタに要する領域は極めて小さいが、サイズ n のリストの添字を表すには一般に O(log n)ビットの領域を必要とする。
この定義によればヒープソートは in-place であるがイントロソートは O((log n)) の追加領域を必要とするため in-place ではないということになる。
Lクラスのアルゴリズムを in-placeアルゴリズムであると認めると、興味深い洞察が得られる。例えば、無向グラフでの2ノード間の経路が存在するかどうかを決定する in-placeアルゴリズムが存在することになる。通常、この問題は深さ優先探索などでは O(n) の追加領域を必要とする。同様に、2部グラフかどうかの判定問題や2つのグラフが同数の連結成分を持つかどうかという問題などに関しても in-placeアルゴリズムが存在することになる。