[解決済み] サイズnとmの2つのソートされた配列をマージする際の時間複雑度

質問

サイズnとmの2つのソートされた配列をマージする場合の時間的な複雑さはどの程度でしょうか？ nは常にmより大きい .

私はマージソートを使おうと思っていたのですが、この場合、O(log n+m)を消費すると思います。

私はビックオーとかがあまり得意ではありません。この問題の時間計算量と、さらに最適化された解法があれば教えてください。

どのように解決するのですか？

注意! この回答にはエラーが含まれています

より効率的なアルゴリズムが存在し、それは別の回答で紹介されています。

計算量はO(m log n)である。

という長い配列があるとします。 a で、短い配列は b とすると、あなたが説明したアルゴリズムは、次のように書くことができます。

  for each x in b
      insert x into a

ループはm回繰り返される。ソートされた配列への各挿入はO(log n)の処理である。したがって、全体の複雑さはO (m log n)である。

以来 b はソートされているので、上記のアルゴリズムをより効率的にすることができます。

  for q from 1 to m
      if q == 1 then insert b[q] into a
      else 
         insert b[q] into a starting from the position of b[q-1]

これで漸近的な複雑さが改善されるのでしょうか？そうでもありません。

の要素があるとします。 b に沿って均等に広がっています。 a . そうすると、各挿入は O(log (n/m)) となり、全体の複雑さは O(m log(n/m) ) . 定数が存在する場合 k>1 に依存しない n または m そのような n > k * m では O(log(n/m)) = O(log(n)) となり、上記と同じ漸近的な複雑さが得られます。