In-placeアルゴリズム

in-placeアルゴリズムとは、計算機科学においてデータ構造の変換を行うにあたって、追加の記憶領域をほとんど使わずに行うアルゴリズムを意味する。 in-place とは「その場で」といった意味であり、入力が出力で上書きされることが多いことから来る用語である。 in-place でないアルゴリズムは not-in-place あるいは out-of-place などと呼ばれることもある。 in-placeの定義にはやや揺れがある。最も狭義にはポインタなども含めて一定の空間しか使用しないアルゴリズムを指す。しかし長さnの配列の添字を表すだけでも O(log n) の空間を必要とするため、この意味で in-place であるアルゴリズムはごく限られている。多くの場合、 O(log n) の空間を使うことが許される。より広く O((log n)const.) 程度まで認めることもあり、時には o(n) であればよいとすることもある。 入力を出力で上書きしない場合、出力を追加の記憶領域とみなすかどうかについても揺れがある。出力先が通常の記憶装置である場合は記憶領域に含めて評価するが、書き込み専用メモリやストリームに出力する場合にはその大きさを無視して作業領域だけを評価することがある。特に対数領域帰着のような計算複雑性理論の問題では出力空間を無視するのが一般的である（その場合、出力をライトオンリーとすることが本質的に必要である）。