1

一般的に空間の複雑さを分析することについて少し混乱しています。「アルゴリズムによって占有される余分なスペース」の意味がわかりません。1 のスペースとしてカウントされるのは何ですか? ここの例では

int findMin(int[] x) {
    int k = 0; int n = x.length;
    for (int i = 1; i < n; i++) {
        if (x[i] < x[k]) {
            k = i;
        }
    }
    return k;
}

スペースの複雑さは O(n) で、配列サイズが n のためだと推測しています。

しかし、ヒープソートのようなものでは、O(1) かかります。インプレース ヒープソートにもサイズ n (n は入力のサイズ) の配列が必要ではないでしょうか? それとも、入力がすでに配列にあると想定していますか? なぜヒープソートの空間複雑度は O(1) なのですか?

ありがとう！

4

2 に答える 2

1

ヒープソートには、一定量の補助記憶装置しか必要ないため、O(1). ソートされる入力によって使用されるスペースはもちろんO(n).

于 2012-12-27T06:54:39.853 に答える
0

実際には、余分なスペースは、アルゴが使用する追加のスタック スペース、つまり入力以外のスペースに対応し、通常、再帰関数呼び出しでスタックが必要です。アルゴに再帰が存在する場合は、終了条件によって解決されるまでスタックを使用して内容を保存します。

スタックのサイズは O(再帰木の高さ) になります。

これが役に立てば幸いです!!

于 2013-04-30T03:56:28.623 に答える