1

アイデアは、最初の k/2 リストと 2 番目の k/2 リストを再帰的にマージし、次にマージされた 2 つのリストを 1 つのリストにマージして返すことです。

最初の k/2 を 2 番目の k/2 リストと再帰的にマージすることが何を意味するのか混乱しています。誰かがこれを明確にしたり、この再帰を説明する疑似コードを調べたりできますか?

4

1 に答える 1

2 
List recursiveMerge(List[] lists)
{
  // Easy to solve problem for up to length 2
  if (lists.length < 1)
  {
    return new List();
  }
  if (lists.length == 1)
  {
    return lists[0];
  }
  if (lists.length == 2)
  {
    return baseMerge(lists[0], lists[1]);
  }
  // For longer lengths split the array into two
  int half = lists.length / 2;
  List[] firstHalf = new List[half];
  List[] secondHalf = new List[lists.length - half];
  System.arraycopy(lists, 0, firstHalf, 0, firstHalf.length);
  System.arraycopy(lists, firstHalf.length, secondHalf,
    0, secondHalf.length);
  // Solve the problem separately in each sub-array
  List a = recursiveMerge(firstHalf);
  List b = recursiveMerge(secondHalf);
  // and produce a combined solution
  return baseMerge(a, b);
}

N 個のリスト 0,1,2,3... から始めると、再帰ツリーの最下部で、0 を 1 に、2 を 3 に、4 を 5 に、というようにマージします。次のステップでは、0+1 を 2+3 に、4+5 を 6+7 に、というようにマージします。したがって、N 個のリストがある場合、ツリーには lg(N) レベルがあり、それぞれが各データ ポイントを 1 回処理します。したがって、全長 L のリストが N 個ある場合、コストは O(L log(N)) になります。

于 2012-09-16T04:52:28.683 に答える