類似：Time complexity for merging two sorted arrays of size n and mしかし、ソートされていません。サイズnとmの2つのソートされていない配列をマージするための時間の複雑さ
私はこの操作の時間の複雑さを困惑させようとしています。
サイズの異なる2つの配列がありますが、常に大きなサイズの配列にマージされます。だからnはいつもmより大きい。 Array 1にマージするたびに、Array 2からその要素を削除するたびに、Array 2を短くして、各配列要素の単一のプロパティに基づいてマージしています。
これはBig O表記とは何でしょうか？
両方のアレイを並べ替えます。 O(nlogn + mlogm) = O(nlogn)（n > m以降）と仮定できますが、キーが整数であるか、または利用できる他のプロパティがある場合、ソート部分の理論的な下限値はO(n + m) = O(n)に近づく可能性があります。
マージでは、ソートされた配列をマージするためにアレイを一度スキャンするだけで済むので、O(n + m) = O(n)を費やすだけです。
つまり、ソートにかかる時間が支配的になりますが、これはあなたがこのアルゴリズムを選択した場合のみです。
mを直線的にそれぞれnのように検索するように見えます。平均して、適切なポジションはm途中にあります。すなわち、操作の数がn×m個/ 2に近いが、ビッグO記法は線形定数を無視し、自分の複雑コメントで述べたように
O(mn)
なります。
私はクヌスが美学を認めているとは思わないが、少なくともあなたはそのアイデアを得る。 :-)
big-O表記で「2で除算」部分を指定する必要はありません。定数乗数はbig-Oが表すものの一部ではありません。 – Nick
log(n) > mの場合、ダムリニア検索を行い、O(m * n)の複雑さがある方が良いです。
それ以外の場合は、配列1をソートしてから、高速検索を実行してO(n log n)（ソート時間のみ）にすることができます。挿入物はまだ支配するかもしれないです。
他のqでは「マージ」するため、問題についてさらに詳しく知りたい。特に、ソートされた配列を他の2つのソート済み配列から作成することを指します。出力をソートするか、そうでなければその注文について気にしますか？両方の配列に表示される項目を出力に1回だけ表示するか、2回表示するかを選択しますか？ – twotwotwo
この問題の制限事項の一部を少しピンチできますか？たとえば、追加の補助データ構造を割り当てて、マージに役立てることができますか？それは許可されていませんか？ – templatetypedef
@twotwotwo出力をソートする必要はありません。私は小さな配列のオブジェクトを大きな配列のオブジェクトにマージしています（配列1の長さを増やさない）。次に、配列2から要素を削除する。 2つの名前リストがあると考えると、誕生日、および他のリストは好きな色を持っています。私は名前に基づいてオブジェクトをマージします。 –