为什么合并排序中的合并操作为O(n)? [英] Why Merge Operation in Merge Sort is O(n)?

问题描述

对于合并排序分割和征服操作，自下而上的合并阶段需要多少时间?我的老师说这是线性的，因此它是O(n).但是我不明白.线性如何?

合并操作如何成为线性O(n)?

解决方案

两个数组的合并操作，即扫描数组并选择两个中的最低/最高值.

所以你有

a: [1, 3, 6, 7]
b: [4, 5, 7, 8]

您这样比较(某种伪代码)

indexA = 0;
indexB = 0;
auxilaryArray = [];
indexAux = 0;

while true 
   if indexA > len(a)-1 or indexb > len(b) -1  
       break
   # you are cherry picking one from the two array which is lesser
   # until any one of these array exausts
   if(a[indexA] > b[indexB])
       auxilaryArray[indexAux++] = b[indexB++]
   else
       auxilaryArray[indexAux++] = a[indexA++]

#append the remaining array 
while indexA < len(a)
    auxilaryArray[indexAux++] = a[indexA++]

#appends the remaining array
while indexB < len(b)
    auxilaryArray[indexAux++] = b[indexB++]

您将看到数组a[k]和b[m]三个循环的迭代总和 是否为k+m.

---

万一

a: [1, 3, 6, 7]
b: [4, 5, 7, 8]

这是第一个循环:

(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2) # 6 iterations; array a exhausted

由于已扫描a，因此第二个循环未运行.

第三个循环追加

b[2], b[3]   # 2 iterations; b exhaused

您看到8 = 4 + 4循环正在运行吗? O(n)是什么顺序.

---

在Mergesort中，除法运算是对数的，ln n-合并部分是线性的.由于您进行了划分和合并，因此顺序变为可乘的，因此Mergesort为O(nln(n)).

与冒泡，选择，插入排序不同，在其中您从左到右扫描(O(n))，然后通过连续交换(冒泡)或通过扫描未排序数组的其余部分中的最小值(选择)来拟合合适的候选对象，或通过在数组的排序部分中的正确位置插入(插入)-这些操作为O(n)...，因此这些算法的总体顺序为O(n ² )

For merge-sort divide and conquer operations, how much time is required in bottom up merging phase? My instructor says that it is be linear, hence it will be O(n). But I didn't get it. How will it be linear?

How will merging operation be linear O(n)?

解决方案

Merge operation of two arrays, is scanning arrays and picking the lowest/highest of two.

so you have

a: [1, 3, 6, 7]
b: [4, 5, 7, 8]

you compare like this (sort of pseudo code)

indexA = 0;
indexB = 0;
auxilaryArray = [];
indexAux = 0;

while true 
   if indexA > len(a)-1 or indexb > len(b) -1  
       break
   # you are cherry picking one from the two array which is lesser
   # until any one of these array exausts
   if(a[indexA] > b[indexB])
       auxilaryArray[indexAux++] = b[indexB++]
   else
       auxilaryArray[indexAux++] = a[indexA++]

#append the remaining array 
while indexA < len(a)
    auxilaryArray[indexAux++] = a[indexA++]

#appends the remaining array
while indexB < len(b)
    auxilaryArray[indexAux++] = b[indexB++]

you see if array a[k], and b[m] the sum of iterations by the three loops will be k+m.

---

In case

a: [1, 3, 6, 7]
b: [4, 5, 7, 8]

Here is the first loop for this:

(0, 0), (1, 0), (2, 0), (2, 1), (2, 2), (3, 2) # 6 iterations; array a exhausted

The second loop does not run since a is already scanned.

The third loop appends

b[2], b[3]   # 2 iterations; b exhaused

You see 8 = 4 + 4 loops running? What's the order O(n).

---

In Mergesort the divide operation is logarithmic, ln n -- the merge part is linear. Since you divide and merge back the order becomes multiplicative so Mergesort is O(nln(n)).

Unlike Bubble, Selection, Insertion sort where you scan left to right (O(n)) and then fit the right candidate by consecutive swaps (bubble), or by scanning the minimum in rest of the the unsorted array (selection), or by inserting at right place in sorted part of the array (insertion) -- these operations are O(n)... so the overall order of these algos becomes O(n²)

这篇关于为什么合并排序中的合并操作为O(n)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！