1

nノードと高さを備えた完全にバランスの取れたバイナリ ツリーで機能する再帰関数がlog(n)あり、ツリーのルートで以下の関数を呼び出すとします。

void printPaths(TreeNode root, int[] array, int depth){
    if (root == null){
        print array;
    }
    array[depth] = root.data;
    printPaths(root.left, array, depth + 1);
    printPaths(root.right, array, depth + 1);
}

array = new int[depthOfTree]
printPaths(root, array, 0);

配列を長さlog(n)とします (ツリーのパスに沿って値を格納します)。再帰呼び出しスタックが max height になることはわかっていますlog(n)。Java の「値渡し」の性質と Java ガベージ コレクションが時間と空間の複雑さにどのように影響するのか、私にはよくわかりません。

1) 配列を再帰呼び出しに渡す時間の複雑さは? Java が「値渡し」の場合、各再帰呼び出しはO(log(n))、関数の実行を開始する前に配列をコピーするだけで済みますか?

2) これらの配列のコピーがメモリ内で一度にいくつ浮遊するかの上限は? 私の傾向は言うことO(log(n))です。それは空間の複雑さが であることを意味しますO(log(n)log(n))か? O(log(n))「スペースの複雑さは、アルゴリズムが再帰O(log(n))回数を繰り返し、パスパラメーターがO(log(n))再帰中にスペースで1回だけ割り当てられるためです」という本を読んだことがあります。

4

2 に答える 2

5

1) 配列を再帰呼び出しに渡す時間の複雑さは? Java が「値渡し」の場合、関数の実行を開始する前に、再帰呼び出しごとに O(log(n)) を使用して配列を単純にコピーしますか?

ちょうどO（1）。参照は値渡しです。配列は参照型です (配列の要素型が値型であっても、たとえば の場合int[])。

したがって、array式の値は配列オブジェクト自体ではなく、単なる参照です。

2) これらの配列のコピーのうち、一度にメモリ内に浮かぶ数の上限は?

同じ理由でちょうど 1 です。1 つの配列があり、スタック内の各レベルはそれへの参照を持っています。

各再帰ステップで使用される唯一の余分なメモリは、スタック上のローカル変数の値に十分なスペースです...これは、呼び出しごとに一定量のスペースです。O(log(N)) の深さで、これは O(log(N)) のスペースの複雑さも意味します。

于 2013-07-24T05:17:41.137 に答える
1

1) 配列を再帰呼び出しに渡す時間の複雑さは? Java が「値渡し」の場合、関数の実行を開始する前に、再帰呼び出しごとに O(log(n)) を使用して配列を単純にコピーしますか?

Java は配列をコピーしません。Java では、Object の参照をメソッドの引数として渡します。したがって、オブジェクトのデータが変更されると、それを参照するすべての参照に反映されます。

于 2013-07-24T05:19:32.600 に答える