algorithm - リストからのアイテムの削除-アルゴリズムの時間計算量

Question

問題は、サイズnとmの重複がない2つのソートされたリストで構成されています。最初のリストには、2番目のリストから削除する必要のある文字列が含まれています。

最も単純なアルゴリズムはnxm操作を行う必要があります（これの用語は「二次時間」だと思いますか？）。

改善された解決策は、両方のリストがソートされ、将来の比較で最後に削除されたインデックスよりも低いインデックスを持つ文字列をスキップするという事実を利用することです。それは何時の複雑さでしょうか？

より複雑な時間でこの問題の解決策はありますか？

Answer 1

Merge sortを調べる必要があります。これが、効率的に機能する理由の背後にある基本的な考え方です。

アイデアは、2 つのリストを一緒にスキャンすることですが、これには時間がかかりますO(n+m)。

xたとえば、最初のリストのポインターと、2 番目のリストのA別のポインターを作成します。と を設定します。whileおよびifの場合、新しいマージされたリストに追加し、 をインクリメントします。それ以外の場合は、新しいリストに追加してインクリメントします。またはをヒットしたら、それぞれまたはから残りの要素を取得します。yBx=0y=0x < ny < mA[x] < B[y]A[x]xB[y]yx=ny=mBA

Answer 2

O(n+m)各リストのすべての項目が 1 回だけアクセスされるため、複雑さは になると思います。

Answer 3

カウント/バケット ソート アルゴリズムは、2 番目のリストの各文字列がバケットである場合に機能します。

2 番目のリストを調べて (m 時間かかります)、バケットを作成します。次に、最初のリストを調べて (n 時間かかります)、出現回数を増やします。次に、各バケットをもう一度調べて (m 時間かかります)、1 回出現する文字列のみを返す必要があります。Trie または HashMap は、バケットの格納に適しています。O(n+m+m) である必要があります。HashSet を使用する場合、カウンターをインクリメントする代わりに 2 番目のパスで Set から削除します。O(n+m+(mn)) である必要があります。

Answer 4

二分探索を使えば O(m + log(n)) ではないでしょうか？