サイズ n のセット A とセット B があり、セット A のすべてのカードに対して、セット B に対応するカードがあります。
平均的なケースの複雑度が O(nlogn) のテストで一致するペアを見つける、より効率的なアルゴリズムを説明してください。アルゴリズムが必要な複雑さを満たしていることを証明します。
クイックソートを使用して各セットを並べ替えることができると考えています。これはnlogn + nlognであり、各セットの対応する位置が一致するペアであることがわかります。これは正しいでしょうか？これが問題の全体です
各セットは n 枚のカードで構成され、セット A のすべてのカードに対して、同じアカウントに属するセット B に対応するカードがあり、これら 2 枚のカードを一致するペアと呼びます。各カードは、銀行の一意の口座に対応する暗号化された番号を持つ磁気ストリップを含む小さなプラスチック製のオブジェクトです。一致するすべてのペアを見つける必要があります。セット A から 1 枚とセット B から 1 枚の 2 枚のカードがマシンに挿入されると、3 つのライト インジケータの 1 つが点灯するカード リーダー マシンがあります。ペアが一致する場合は緑、A の口座番号が B より大きい場合は赤、B の番号が A より大きい場合は黄色です。ただし、カード リーダーは同じセットに属する 2 枚のカードを比較することはできません。