[解決済み] マージソートの時間および空間の複雑さ

質問

Merge Sortの実装を例にして説明します。

void mergesort(Item a[], int l, int r) {
if (r <= l) return;
int m = (r+l)/2;
mergesort(a, l, m);   ------------(1)
mergesort(a, m+1, r); ------------(2)
merge(a, l, m, r);

a) このマージソートの時間的複雑さは O(n lg(n)) . (1) と (2) を並列化することで、実用的な利得が得られるのでしょうか？理論的には、(1)と(2)を並列化した後に O(n lg(n)) . しかし、現実的に何か得るものがあるのでしょうか？

b) このMerge Sortの空間的な複雑さは以下の通りです。 O(n) . しかし、リンクリストを使用してインプレース・マージソートを実行すると（配列で合理的に実行できるかどうかは分かりません）、空間の複雑さは次のようになります。 O(lg(n)) 再帰処理スタックのフレームサイズを考慮する必要があるため？ また O(lg(n)) 64以上にはならないので、定数として？何箇所か誤解しているところがあるかもしれません。64というのは具体的にどういう意味でしょうか？

c) ソートアルゴリズムの比較 - Cprogramming.com マージソートはリンクリストを使用するため、一定のスペースが必要であると言われています。どのように？彼らは O(lg(n)) を一定にするのですか？

d) より分かりやすくするために追加しました。 空間の複雑さの計算では、入力の配列やリストがすでにメモリ内にあると仮定するのが妥当でしょうか？私は複雑さの計算をするとき、入力によってすでに占有されているスペース以外に必要となる余分なスペースを常に計算します。そうしないと、空間の複雑さは常に O(n) またはそれ以上です。

解決方法は？

a) そうです。完璧な世界では、サイズn, n/2, n/4 ...の対数n個のマージを行う必要があります。(あるいは、1, 2, 3 ... n/4, n/2, n - これらは並列化できません) で、O(n) を与えます。それでもO(n log n)である。完璧とは言えない世界では、プロセッサの数が無限にあるわけではありませんし、コンテキストスイッチや同期が潜在的な利益を打ち消すからです。

b) 要素をどこかに保存しなければならないので、空間の複雑さは常にΩ(n)である。配列の実装ではO(n)、リンクリストの実装ではO(1)になります。実際には、リストを使用する実装では、リストのポインタのために追加のスペースが必要です。

編集 スタックフレームを数えるなら、O(n)+O(log n)なので、配列の場合はまだO(n)です。リストの場合は、O(log n)の追加メモリとなります。

c) リストは、マージ処理中にいくつかのポインタを変更する必要があるだけです。これには一定の追加メモリが必要です。

d) マージ・ソートの複雑性分析で、「追加的なスペース要件」などに言及されるのはそのためです。要素をどこかに保存しなければならないのは明らかですが、純粋主義者を寄せ付けないためには、常に「追加メモリ」について言及する方がよいのです。