3

Mサイズがとの 2 つの並べ替えられていない単一のリンクされたリストが与えられNます。タスクは、単一の並べ替えられたリンク リストを作成することです。新しいノードは作成しないでください。私は2つのアプローチを考えました。

アプローチ 1:

各リストを MlogM と NlogN で個別に並べ替えます。次に、ソートされた 2 つのリストをマージします。
時間計算量: O( MlogM + NlogN )

アプローチ 2:

最初のリストの最後に 2 番目のリストを追加します。次に、リストを並べ替えます。
時間の複雑さ: O( (M + N) log(M + N) )

どちらのアプローチが優れていますか?
より良いアプローチはまだありますか？

4

2 に答える 2

4

漸近的に言えば、それは同じです。

その場合n<m：

O(nlogn+ mlogm) = O(mlogm)
and 
O(n+m)log(n+m)) = O(nlog(n+m) + mlog(n+m)) = O(nlog(m) + mlog(m)) = O(mlogm)

対称的に、m<n両方がO(nlogn)

実際、の場合n=m、アプローチ1はマージソートの最初のステップです

于 2012-09-05T17:19:12.877 に答える
0

いずれにせよ、アプローチ1が良いです。この計算を参照してください。

  • n=2 および m=3 nlogn = 0.60、mlogm = 1.43、nlogn + mlogm = 2.03 (n+m)log(n+m) = 3.49

  • n=2 および m=30 nlogn = 0.60、mlogm = 44.31、nlogn + mlogm = 44.91 (n+m)log(n+m) = 48.16

  • n=2 および m=300 nlogn = 0.60、mlogm = 743.14、nlogn + mlogm = 743.74
    (n+m)log(n+m) = 748.96

  • n=2 および m=3000 nlogn = 0.60、mlogm = 10,431.36、nlogn + mlogm =
    10,431.96 (n+m)log(n+m) = 10,439.18

  • n=2 および m=30000 nlogn = 0.60、mlogm = 134,313.64、nlogn + mlogm =
    134,314.24 (n+m)log(n+m) = 134,323.46

  • n=2 および m=300000 nlogn = 0.60、mlogm = 1,643,136.38、nlogn + mlogm = 1,643,136.98 (n+m)log(n+m) = 1,643,148.19

なぜなら、この背後にある明確な理由は次のとおりです。いずれにせよ、

(n+m) > n & (n+m) > m
log (n+m) >= log n
log (n+m) >= log m

一方、n=mの場合、

nlogn + mlogm = 2m logm
              = log m (power of 2m)
(n+m) log(n+m) = 2m log (2m)
               = log 2m (power of 2m)
and m(power of 2m) < 2m(power of 2m)

最初のアプローチを選択する唯一の単純な理由は、大きな大きな配列と比較して、データの小さな配列をソートする方が時間がかからないことです。

于 2012-09-07T09:54:24.333 に答える