7

2 つの降順リスト (list1 と list2) の和集合を見つける必要があります。ここで、和集合は、重複のない両方のリストの各要素になります。リスト要素が整数であると仮定します。この問題を解決するための最も効率的なアルゴリズムを決定するために、大きな O 表記を使用しています。1stの大文字オー表記は知っていますが、2ndのビッグオー表記は知りません。実装するアルゴリズムを決定できるように、誰かが2番目のアルゴリズムの大きなO表記を教えてもらえますか? 誰かがこれらのアルゴリズムよりも優れたアルゴリズムを知っている場合は、それを理解するのを手伝ってもらえますか? 前もって感謝します。

Here are my two algorithms. . .

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Algorithm #1: O(N * log base2 N)

Starting at the first element of list1, 
while(list1 is not at the end of the list) {
    if(the current element in list1 is not in list2)    // Binary Search -> O(log base2 N)
        add the current element in list1 to list2
    go to the next element in list1 }

list2 is now the union of the 2 lists

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Algorithm #2: O(?)

Starting at the first elements of each list,
LOOP_START:
    compare the current elements of the lists
    whichever element is greater, put into a 3rd list called list3
    go to the next element in the list whose element was just inserted into list3
    branch to LOOP_START until either list1 or list2 are at the end of their respective list
insert the remaining elements from either list1 or list2 into list3 (the union)

list3 now contains the union of list1 and list2
4

8 に答える 8

8

2 番目は O(n+m) で、最初は O(n log(m) + m) です。したがって、2 番目の方がはるかに優れています。

于 2013-03-18T06:22:57.147 に答える
8

これが私の状況の評価です

  • 最初のアルゴリズムはn log n時間で実行されます。最初のリストのすべての要素に対して二分探索を行っていますよね?
  • 2 番目のアルゴリズムは完全ではありません。2 つのリストの要素が等しい場合に何をすべきかを示していません。ただし、等しい要素を処理するための適切なロジックが与えられた場合、2 番目のアルゴリズムはマージ ソートのマージ部分のようなものです。つまり、線形時間 (つまりN) で実行されます。それ以上のことはできないという意味で、これは最適です: 両方のリストのすべての要素を少なくとも 1 回見なければ、2 つの順序付けられたリストをマージすることはできません。
于 2013-03-18T06:23:43.440 に答える
1

次のアルゴリズムを使用すると、2 つのリストを O(n+m) にマージできます。

[申し訳ありませんが、簡単にするために python を使用しましたが、アルゴリズムはどの言語でも同じです]

アルゴリズムは、結果リストでソートされたアイテムも維持することに注意してください。

def merge(list1, list2):
    result = []
    i1 = 0;
    i2 = 0;
    #iterate over the two lists
    while i1 < len(list1) and i2 < len(list2):
        #if the current items are equal, add just one and go to the next two items
        if list1[i1] == list2[i2]:
            result.append(list1[i1])
            i1 += 1
            i2 += 1
        #if the item of list1 is greater than the item of list2, add it and go to next item of list1
        elif list1[i1] > list2[i2]:
            result.append(list1[i1])
            i1 += 1
        #if the item of list2 is greater than the item of list1, add it and go to next item of list2
        else:
            result.append(list2[i2])
            i2 += 1
    #Add the remaining items of list1
    while i1 < len(list1):
        result.append(list1[i1])
        i1 += 1
    #Add the remaining items of list2
    while i2 < len(list2):
        result.append(list2[i2])
        i2 += 1
    return result

print merge([10,8,5,1],[12,11,7,5,2])

出力：

[12, 11, 10, 8, 7, 5, 2, 1]
于 2013-12-10T22:12:40.120 に答える
0

実際には、入力リストがソートされていない場合、アルゴリズム 2 は機能しません。配列をソートするには、次の順序で O(m*lg(m)+ n*lg(n))

最初のリストでハッシュ テーブルを作成し、次に 2 番目のリストの各アイテムについて、このアイテムがハッシュ テーブルに存在するかどうかを確認します。これは O(m+n) で機能します。

于 2013-12-10T20:54:55.777 に答える
0

指定する必要があるものがいくつかあります。

  • 入力リストに重複が含まれていますか?
  • 結果を順序付けする必要がありますか?

std::listを使用すると、先頭または末尾に安価に挿入できると仮定します。

リスト 1 に N 個の要素があり、リスト 2 に M 個の要素があるとします。

アルゴリズム 1

リスト 1 のすべての項目を繰り返し処理し、リスト 2 で検索します。

重複がある可能性があり、結果を順序付けする必要があると仮定すると、検索の最悪のケースは、リスト 1 の要素がリスト 2 に存在しないことです。したがって、少なくとも次のようになります。

  • O(N×M)。

リスト 1 の項目を適切な場所に挿入するには、リスト 2 を挿入ポイントまで繰り返す必要があります。最悪のケースは、リスト 1 のすべての項目が小さい場合 (リスト 2 を最初から検索した場合) または大きい場合 (リスト 2 を最後から検索した場合) です。リスト 1 の前の項目がリスト 2 に挿入されているため、最初の項目は M 回、2 番目は M + 1 回、3 番目は M + 2 回、最後の項目は M + N - 1 回の繰り返しになります。アイテムあたりの平均は M + (N - 1) / 2 です。

何かのようなもの：

  • N × (M + (N - 1) / 2)

big-O 表記の場合、定数係数は重要ではないため、次のようになります。

  • N × (M + (N - 1))

big-O 表記の場合、非変数の追加は問題にならないため、次のようになります。

  • O(N × (M + N))

元の O(N × M) に追加:

  • O(N × M) + O(N × (M + N))
  • O(N × M) + O(N × M + N 2 )

2 番目の方程式は、たとえば 2 × (N × M) などの定数因子の除去を明らかにするためのものです。したがって、

  • O(N × (M + N))
  • O(N 2 + N × M)

これら 2 つは同等で、どちらが好きかを示します。

可能な最適化:

  • 結果を順序付けする必要がない場合、挿入は O(1) になる可能性があるため、最悪の場合は次のようになります。

    • O(N×M)

  • リスト 2 のリスト 1 の各項目を等しいかどうかだけでテストしないでください。たとえば、各項目がより大きいかどうかをテストして、リスト 1 の項目がリスト 2 の項目よりも大きい場合にリスト 2 での検索を停止できるようにします。これは最悪のケースを減らすことにはなりませんが、平均的なケースを減らすことになります

  • リスト 1 の項目がリスト 2 の項目よりも大きいことがわかった場所を指すリスト 2 反復子を保持して、ソートされた挿入を O(1) にします。リスト 1 は順序付けされていますが、重複が含まれている可能性があるため、挿入時には、挿入されたアイテムで始まる反復子を保持してください。これら 2 つの場合、最悪のケースは次のようになります。

    • O(N×M)

  • 次の反復では、リスト 2 の残りの部分でリスト 1 の項目を、保持した反復子で検索します。リスト 2 の最後に到達すると、リスト 1 から重複を「削除」することになるため、これにより最悪のケースが減少します。これら 3 つの場合、最悪のケースは次のようになります。

    • O(N + M)

この時点で、このアルゴリズムとアルゴリズム 2 の唯一の違いは、リスト 2 が新しいリストを作成するのではなく、結果を含むように変更されていることです。

アルゴリズム 2

これがマージソートのマージです。

リスト 1 のすべての要素とリスト 2 のすべての要素を 1 回ずつ移動し、挿入は常にリストの先頭または末尾で行われるため、最悪の場合の時間は次のようになります。

  • O(N + M)

重複がある場合は、単に破棄されます。結果は、注文されないよりも簡単に注文されます。

ファイナルノート

重複がない場合は、どちらの場合も挿入を最適化できます。たとえば、二重にリンクされたリストを使用すると、リスト 1 の最後の要素がリスト 2 の最初の要素より大きいかどうか、またはその逆かどうかを簡単に確認でき、リストを単純に連結できます。

これは、リスト 1 とリスト 2 の末尾に対してさらに一般化できます。たとえば、アルゴリズム 1 では、リスト 1 の項目がリスト 2 で見つからない場合、リスト 2 とリスト 1 の末尾を連結できます。アルゴリズム 2 では、これは最後のステップで行われます。

リスト 1 の項目とリスト 2 の項目が交互に配置されている最悪のケースは削減されませんが、平均的なケースでは削減され、多くの場合、Real Life™ に大きな違いをもたらす大きな要因によって削減されます。

私は無視しました：

  • 割り当て時間
  • アルゴリズムのより悪いスペースの違い
  • 配列やツリーではなく、リストに言及したため、バイナリ検索

明らかな間違いを犯さなかったことを願っています。

于 2013-12-10T23:42:48.583 に答える
0

複雑さの分析:

リスト 1 の長さが でNあり、リスト 2の長さが であるとしMます。

アルゴリズム 1:
信じられないように聞こえるかもしれませんが、このアルゴリズムの複雑さN * MはNlogM.

リスト 1 の各要素について(O(N))、リスト 2 で検索しています(O(logM)。このアルゴリズムの複雑さは「思われる」O(NlogM).

ただし、リスト 2 にも要素を挿入しています。この新しい要素を適切な場所に挿入して、リスト 2 がさらに二分探索操作のためにソートされたままになるようにする必要があります。データ構造として配列を使用している場合、挿入には時間がかかりO(M)ます。

したがって、複雑さの順序はO(N*M)アルゴリズムそのままです。

新しい要素がリスト 2 の末尾に挿入され (その後、リストは順序付けされなくなります)、.0 to M-1ではなくインデックスからバイナリ検索操作を実行する変更を行うことができnew size-1ます。この場合、長さのリストでバイナリ検索をO(N*logM)実行するため、複雑さは次のようになります。NM

リストを再度順序付けするには、順序付けされた 2 つの部分 (0 から M-1 および M から newSize-1) をマージする必要があります。これは、O(N+M) 時間 (配列長 N+M のマージソートでの 1 つのマージ操作) で実行できます。したがって、このアルゴリズムの正味の時間複雑度は次のようになります。 

O(NlogM + N + M)

スペースの複雑さはO(max(N,M))、元のリストのスペースを考慮しておらず、リスト 2 で必要な余分なスペースのみを考慮しています。

アルゴリズム 2:
各反復で、少なくとも 1 つのポインターを進めます。両方のポインターが移動する合計距離はN + Mです。したがって、最悪の場合の時間の複雑さの順序はO(N+M)、最初のアルゴリズムよりも優れています。

ただし、この場合に必要なスペースの複雑さは大きくなります ( O(N+M))。

于 2013-12-04T11:34:43.013 に答える
0

別の方法を次に示します。両方のリストを繰り返し処理し、すべての値をセットに挿入します。これにより、すべての重複が削除され、結果は 2 つのリストの結合になります。2 つの重要な注意事項: 数字の順序が崩れます。また、追加のスペースが必要です。

時間計算量: O(n + m)

スペースの複雑さ: O(n + m)

結果セットの順序を維持する必要がある場合は、LinkedHashMap のカスタム バージョンを使用します。

于 2013-12-07T09:14:17.483 に答える
0

以前のプロジェクトの 1 つで、オブジェクトの 2 つの配列のユニオン操作の typescript(js) ベースの実装を実装しました。データが大きすぎて、アンダースコアやロダッシュなどのデフォルトのライブラリ関数が楽観的ではありませんでした。いくつかのブレインハンティングの後、以下の二分探索ベースのアルゴリズムを思いつきました。誰かのパフォーマンス調整に役立つことを願っています。

複雑さに関する限り、アルゴリズムは二分探索に基づいており、最終的には O(log(N)) になります。

基本的に、コードは 2 つの順序付けられていないオブジェクト配列と比較するキー名を受け取ります。1) 配列を並べ替えます。2) 最初の配列の各要素を反復処理し、2 番目の配列で削除します。3) 結果の 2 番目の配列を最初の配列に連結します。

    private sortArrays = (arr1: Array<Object>, arr2: Array<Object>, propertyName: string): void => {
        function comparer(a, b) {
            if (a[propertyName] < b[propertyName])
                return -1;
            if (a[propertyName] > b[propertyName])
                return 1;
            return 0;
        }

        arr1.sort(comparer);
        arr2.sort(comparer);
    }

    private difference = (arr1: Array<Object>, arr2: Array<Object>, propertyName: string): Array<Object> => {

        this.sortArrays(arr1, arr2, propertyName);

        var self = this;

        for (var i = 0; i < arr1.length; i++) {
            var obj = {
                loc: 0
            };
            if (this.OptimisedBinarySearch(arr2, arr2.length, obj, arr1[i], propertyName))
                arr2.splice(obj.loc, 1);
        }

        return arr2;
    }

    private OptimisedBinarySearch = (arr, size, obj, val, propertyName): boolean => {
        var first, mid, last;
        var count;

        first = 0;
        last = size - 1;
        count = 0;

        if (!arr.length)
            return false;
        while (arr[first][propertyName] <= val[propertyName] && val[propertyName] <= arr[last][propertyName]) {
            mid = first + Math.floor((last - first) / 2);

            if (val[propertyName] == arr[mid][propertyName]) {
                obj.loc = mid;
                return true;
            }
            else if (val[propertyName] < arr[mid][propertyName])
                last = mid - 1;
            else
                first = mid + 1;
        }
        return false;
    }

    private UnionAll = (arr1, arr2, propertyName): Array<Object> => {
        return arr1.concat(this.difference(arr1, arr2, propertyName));
    } 

    //example
    var YourFirstArray = [{x:1},{x:2},{x:3}]
    var YourSecondArray= [{x:0},{x:1},{x:2},{x:3},{x:4},{x:5}]
    var keyName = "x";
    this.UnionAll(YourFirstArray, YourSecondArray, keyName)
于 2017-01-02T15:12:58.627 に答える