私は彼の質問のポスターに感謝し、時間の複雑さと空間の複雑さが互いにどのように反対しているかの実例を提示したいと思います。大量のスペースがあれば、アルゴリズムは非常に高速になります（「状態」を作成できるため）。逆に、スペースが非常に限られている場合は、状態の不足を補うために余分な繰り返しを実行する必要があります。
この問題は、空間の複雑さO（n）で解くのが容易であることが分かります。結果（O（n））のためのスペースを作成することが許可されている場合、時間複雑度O（n）で解を作成できるいくつかのアルゴリズムがあります。 1つの解決策が掲載されています（私が好きです）。また、O（n）と時間複雑度O（n）を解くために、異なる、おそらくエレガントなアプローチを提供します。メソッドsolveOrderN（）を参照してください。
難問は、O（n）未満の空間複雑度の解を見つける方法です。これを行うには、結果スペースを作成することを許可されてはならず、結果として、その質問に示されたツリースペース内で操作することが強制されます。要素をスワップする必要があります。
解決策 - solveSubOrderN（） - は結果空間を作成しません。答えは質問と同じメモリ空間に返されます。
私は非常に楽観的でした。私はO（log base 2（n））とO（n）に近い時間的複雑さでもこの問題を解決できました。しかし、多くの分析の後、私はこれを積極的にすることはできません。
要素の入れ替えを開始すると、処理不能な要素に戻るときに、最終的に「停止状態」になります。この停止が存在しない場合は、O（ログベース2 n）を達成できます。しかし、あなたはそれを避けることはできません。そこで、これを補うために、処理中の要素の状態を表すスペース（ブール値の配列）を作成することを余儀なくされました。
このブール値の状態が、結果/解決策のためのスペースを作成することとどう違うかについて、お話したいと思います。解（n個の要素、サイズs）のために作成するときは、スペース= n * sを作成しています。この質問では、sは整数です。一般的には非常に大きく、「高価な」プロセス（そしてポスターがこの問題を引き起こした理由）になります。ブール値の配列の空間はかなり小さく、sのサイズが大きくなるにつれ無視できるほどです（つまり、n/sは、sが大きくなるにつれて0に近づきます）。
また、空間の複雑さがO（n）より小さい場合、時間の複雑さO（n）を達成できないことが分かります。停止状態になると、再度反復する必要があります。しかし、バイナリツリーの場合、余分な反復の量は少ない（各反復は単に次の開始点を見つけることである）ことが判明した。
要約すると、以下の2つの解決策を見つけてください。 1つは、空間複雑度O（n）および時間複雑度O（n）を有するが、より重要なことは、O（n）に非常に近い時間複雑さを有する空間複雑度がO
public class BinaryTree {
public static void main(String[] args) {
int treeN2[] = {1, 2, 3};
int treeN3[] = {1, 2, 3, 4, 5, 6, 7};
int treeN4[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
int treeN5[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31};
int answer[] = solveOrderN(treeN5);
System.out.println(Arrays.toString(answer));
solveSubOrderN(treeN5);
System.out.println(Arrays.toString(treeN5));
}
/**
* Given a binary tree, Perform inward spiral tree traversal.<br>
* With this approach, there is no space created for the result.
* All manipulation is done within the original tree<br>
* Some space is created (boolean[n]) to add necessary state of processing.
* Space Complexity: Less than O(n), greater than log(base2)(n)
* Time Complexity: Slightly greater than O(n)
* @param tree Input tree
*/
public static void solveSubOrderN(int tree[]) {
boolean complete[] = new boolean[tree.length];
Arrays.fill(complete, false);
System.out.println("Solving Sub O(n); tree size="+tree.length);
int n = log2Round(tree.length+1);
if (n == 1)
return;
int o[] = getLevelOffsets(n);
System.out.println("Number of levels="+n);
int pos = 0;
complete[0] = true;
int currentValue = 0;
int moves=1;
while (moves < tree.length) {
pos = getStartingPos(complete);
currentValue = tree[pos];
tree[pos] = 0;
while (true) {
int nextPos = getTargetPosition(pos, o, n);
int nextValue = tree[nextPos];
tree[nextPos] = currentValue;
complete[nextPos] = true;
currentValue = nextValue;
pos = nextPos;
moves++;
if (currentValue == 0)
break;
}
}
}
/**
* Given a binary tree, Perform inward spiral tree traversal.
* Space Complexity: O(n)
* Time Complexity: O(n)
* @param tree Input tree
* @return The solution
*/
public static int[] solveOrderN(int tree[]) {
int answer[] = new int[tree.length];
int n = log2Round(tree.length+1);
int o[] = getLevelOffsets(n);
System.out.println("Solving O(n); tree size="+tree.length);
System.out.println("Number of levels="+n);
for (int i = 0; i < tree.length; i++) {
answer[getTargetPosition(i, o, n)] = tree[i];
}
return answer;
}
/**
* Search for the first unprocessed element
* @param complete An array of boolean (true = processed)
* @return
*/
public static int getStartingPos(boolean[] complete) {
for (int i=0; i<complete.length; i++) {
if (!complete[i])
return i;
}
return 1;
}
public static int getTargetPosition(int pos, int o[], int n) {
int row = getRow(pos);
int rowOrder = getRowOrder(row, n);
boolean isReversed = isBottom(row, n);
int posInRow = getPosInRow(pos, n);
int rowOffset = getRowOffset(rowSize(row), posInRow, isReversed);
return o[rowOrder]+rowOffset;
}
public static int getRowOffset(int rowSize, int posInRow, boolean isReversed) {
if (!isReversed)
return posInRow;
else
return rowSize-posInRow-1;
}
public static int rowSize(int row) {
return exp(row, 2);
}
public static int getPosInRow(int pos, int n) {
int row = getRow(pos);
return pos-(exp(row,2)-1);
}
/**
* The top n/2 rows print forward, the bottom n/2 rows print reversed
* @param row Zero based row [0 to n-1]
* @param n Number of levels to the tree
* @return true if line should be printed forward, false if reversed
*/
public static boolean isBottom(int row, int n) {
int halfRounded = n/2;
return (row <= n-halfRounded-1) ? false : true;
}
public static int exp(int n, int pow) {
return (int)Math.pow(pow, n);
}
public static double log2(int n) {
return (Math.log(n)/Math.log(2));
}
public static int log2Round(int n) {
return (int)log2(n);
}
/**
* For a given position [0 to N-1], find the level on the binary tree [0 to n-1]
* @param pos Zero based position in the tree (0 to N-1)
* @return Zero based level (0 to n-1)
*/
public static int getRow(int pos) {
return log2Round(pos+1);
}
/**
* For a given row [0 to n-1], find the order in which that line would be processed [1 to log base 2 n]
* @param row The row in the tree [0 to n-1]
* @return The order that row would be processed [0 to n-1]
*/
public static int getRowOrder(int row, int n) {
return isBottom(row, n) ? (n-row-1)*2+1 : row*2;
}
public static int getRowForOffset(int row, int n) {
boolean isOdd = row%2 == 1;
return isOdd ? n-(row-1)/2 - 1 : row/2;
}
/**
* Compute the offset for a given ordered row
* @param n The number of levels in the tree
* @return Generated offsets for each row (to keep time complexity at O(n))
*/
public static int[] getLevelOffsets(int n) {
int o[] = new int[n];
Arrays.fill(o, 0);
o[0] = 0;
int offset = 0;
for (int i=0; i<n; i++) {
int nextRow = getRowForOffset(i, n);
o[i] = offset;
offset += exp(nextRow, 2);
}
return o;
}
}
アイテムを保存する場合は、O（1）ルックアップのパフォーマンスを与えるhashMapを使用することもできます。 –
@MichaelQueueこの場合、HashMapは違いはありません。リストの配列でさえ、各リストのO（1）ルックアップを得るでしょう。 – Atri
こんにちはアトリ、時間があれば、受け入れられる答えがどのように空間O（1）であるか説明してください。 「プリントノード」は、解決策をプリント出力に適合させるためにO（n）スペースが必要であることを意味しないか？ありがとうございました。 –