前回の記事で、
無秩序な集合のバイナリ操作について書いた。 この記事では、順序付きセットの実行の複雑さの少ないアルゴリズムを検討します。
内容
I.順序付きセットの交差II。 順序付きセットの違いIII。 順序付きセットの組み合わせIV。 順序付きセットの対称差おわりにI.順序付きセットの交差
2つの順序セット
Aと
Bの共通部分は、両方のセットに同時に属する要素
Aと
Bのみを含むセットであり、重複はありません。 アルゴリズムの複雑さは
O（m + n）です 。ここで、
mと
nはそれぞれ入力セット
Aと
Bの長さです。
アルゴリズムの動作を示す小さなアニメーションを作成しました。
JavaScriptでの実装例：
function intersec_sort_arr(array_1,array_2) { var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = []; while ((i < n) && (j < m))
関数呼び出し：
intersec_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]);
II。 順序付きセットの違い
2つの順序付きセット
Aと
Bの違いは、
Aの要素が
Bの要素と重複せずに一致しないセットです。 アルゴリズムの複雑さは
O（m + n）です 。ここで、
mおよび
nは
、それぞれ入力順序セット
Aおよび
Bの長さです。
function diff_sort_arr(array_1,array_2) { var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = []; while ((i < n) && (j < m))
diff_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]);
III。 順序付きセットの組み合わせ
2つの順序付けられたセット
Aと
Bの和集合は、
Aの要素とセット
Bの要素を持つセットであり、重複はありません。 アルゴリズムの複雑さは
O（m + n）です 。ここで、
mおよび
nは
、それぞれ入力順序セット
Aおよび
Bの長さです。
function sum_sort_arr(array_1,array_2) { var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = []; while ((i < n) && (j < m))
sum_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]);
IV。 順序付きセットの対称差
2つの順序セット
Aと
Bの対称差は、2番目の順序セットにない最初の順序セットのすべての要素と、1番目の順序セットにない2番目の順序セットの要素を含むセットです。 アルゴリズムの複雑さは
O（2（m + n））です 。ここで、
mおよび
nは
、それぞれ入力順序セット
Aおよび
Bの長さです。
本質的に、これはセットの減算であり、最初に
Aから
B 、次に
Bから
Aの順です。2パス function symmetric_diff_sort_arr(array_1,array_2) { var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = []; while ((i < n) && (j < m))
0leGG によって提案された方法。
1パス function symmetric_diff_sort_arr(array_1,array_2) { var n = array_1.length, m = array_2.length, i = 0, k = 0, j = 0, array_3 = []; while ((i < n) && (j < m))
symmetric_diff_sort_arr([1, 2, 3, 5, 8], [3, 6, 8, 12, 24, 47]);
おわりに
ソートされた配列を頻繁に使用する必要があるため、これらのアルゴリズムはプロセスを大幅に高速化します。
intersec_sort_arrメソッドの実装例は、vk.comの
アプリケーションにあります。 このメソッドを使用すると、数百万の要素でソートされた配列を操作する一般的なコミュニティメンバーが見つかります。このメソッドは非常に迅速に対応します。 その前に、
前の記事で説明した方法を使用しましたが、配列の処理は非常に遅くなりました。