A のアイテムには個別の優先度があり、B のアイテムには個別の優先度があり、(A,B) のペアには結合された優先度があるようです。組み合わせた優先度のみが重要ですが、途中で個々のプロパティを使用できることを願っています。ただし、A の項目と B の項目の間には、独立した優先度の一致関係もあります。
A のすべての a、B の b1 および b2 について、Match(a,b1) および Match(a,b2) の場合、Priority(b1) >= Priority(b2) は CombinedPriority(a,b1) を意味すると仮定します。 >= 複合優先度 (a,b2)。
ここで、B を優先度の高い順に並べ替えることから始めます。B(j) は、この並べ替え順序で j 番目の要素を示します。また、A(i) は A の i 番目の要素を示します (並べ替えられている場合とそうでない場合があります)。
nextb(i,j) を、Match(A(i),B(j')) となるような最小の j' >= j を見つける関数とします。そのような j' が存在しない場合、関数は null (または他の適切なエラー値) を返します。j' を検索するには、j から上方向にループするだけかもしれません。または、Match リレーションの構造について詳しく知っていれば、より速く何かを実行できるかもしれません。
nextb(i,0) != null となるように、A のすべてのインデックス i に対して (i,nextb(i,0)) を含む優先キュー Q を作成します。Q のペア (i,j) は、CombinedPriority(A(i),B(j)) によって並べ替えられます。
Q が空になるまでループします。最も優先度の高いペア (i,j) を取り出し、(A(i),B(j)) を適切に処理します。次に (i,nextb(i,j+1)) を Q に再挿入します (nextb(i,j+1) が null でない場合)。
全体として、すべてのペアが一致する最悪の場合、これには O(N^2 log N) の時間がかかります。一般に、O(N^2 + M log N) かかります。ここで、M は一致の数です。上にループするだけの nextb(i,j) を計算するより高速な方法があれば、N^2 コンポーネントを減らすことができますが、それは Match 関係の知識に依存します。
(上記の分析では、A と B の両方がサイズ N であると仮定しました。サイズが異なる場合、式は簡単に変更できます。)
最悪の場合、O(N^2) 時間よりも優れたものが必要なように見えましたが、すべての一致を処理する必要がある場合は、M の下限があり、N^2 自体である可能性があります。log-N よりも優れた優先順位キューを使用できるように、結合された優先順位に特別な構造がない限り、O(N^2 log N) 時間よりも優れた処理を実行できるとは思いません。