ノート:In-placeアルゴリズム

ソート関連記事との整合性について

この記事では、ソートの個別記事と比べて、追加領域のオーダーがlogn倍されています。
つまり、ヒープソートやシェルソートの記事では追加領域O(1)とされていますが、こちらではO(logn)とされています（英語版でも同様の差異が出ています）。添字表現自体にlognの領域が必要なので、確かにその通りなのですが……。
ソートに限らず、実用的なアルゴリズム関連で「In-place」について知ろうとしている人は、「ヒープソートはO(1)、クイックソートは平均O(logn)の追加領域」ということを念頭に置いているような気がするんですよね。完全に計算量理論寄りの人でないと「ヒープソートはO(logn)、クイックソートは平均O((logn)^2)の追加領域」と言われても直感的でないような。この辺りの整合性をどう取ればよいのか悩みどころです。（素数判定のlogn多項式時間と似たような話ですが、それよりも混乱を来たしやすいのでは……）--Linearithmic（会話） 2021年8月6日 (金) 15:52 (UTC)