[数据结构习题]线性表——数组合并中的时间复杂度

👉知识点导航💎：【数据结构】线性表——顺序存储

👉[王道数据结构]习题导航💎：$page7.10$

本节为线性表的习题

---

$e.g:$

1. 💯移动次数一定为m+n,因为要将两个数组放入到新数组中，每一个元素都需要移动
2. 💯比较的最好情况是一个链表n比另一个链表m短，并且链表n的最大元素比链表m的最小元素小，所以比较次数的时间复杂度是O(min(n,m))

如下图所示:

🎁🎁🎁

很显然，只要把链表n的三个元素分别去跟链表m的第一个元素即4去比较，比较完后再把m链表插在后面，比较的次数就是n的的长度

🎆注意：这里并不是$O(1)$，因为是简单排序，只能从第一个依次向后比较

下面我们再来看看比较的最坏情况

如图：

🔆step：

用双指针，分别指向n[0]和m[0]
 a. 1和2比较，1小，n的指针后移指向n[1]（那下一个和它比较大小），k=1
 b. 2和3比较，2小，m的指针后移，k=2
 c. 3和4比较，3小，n的指针后移,k=3
 d. 4和5比较，4小，m的指针后移,k=4
 e. 5和6比较，5小，n的指针后移,k=5
 f. 6和7比较，6小，m的指针后移,k=6
 g. 7和8比较，7小，n的指针后移,k=7

对于长度相同的数组，我们可以用如下函数实现：

int medium(int* a, int* b, int length) {
    int i = 0, j = 0, k = 0; //用双指针i，j，分别指向两个数组，k用于统计次数( < length-1 )
    for (; k < length - 1; k++) {
        if (a[i] < b[j])
            i++;
        else
            j++;
    }
    return (a[i] < b[j]) ? a[i]:b[j];
}

所以一共比较了$k=m+n-1$ 次

⭐️在最坏情况下，不管n和m是多长，只要相互交错的情况下，比较的次数就是m+n-1

例如下面的情况也是m+n-1

🍰n链表中5从[3,6]比较了3次，8从[6,9]比较了3次，10从[9,11]比较了2次，13最后和11比较了1次，一共是3+3+2+1=9次

💥根据时间复杂度的加法规则：
$O(f(n))+O(g(m))=O(max(f(n),g(m)))$

如: $f(n)=n^3+n^2+n$ 时间复杂度为 $O(n^3)$

3. 💯因此，我们可以得到，最坏时候的时间复杂度为 $O(max(n,m))$

可以很容易得到每次比较必定会归并一个元素,若其中一个有序表的最大元素都小于另一个有序表的最小值，那么只需要比较n次，另一个表直接放入即可，同理最多比较2n-1次

举例：
1 2 3 4 5
6 7 8 9 10 只需要比较5次
1 3 5 7 9
2 4 6 8 10 需要比较9次

🔱结论：

1. 最少比较$min(n,m)$次，最多比较$m+n-1$次
2. 最好时的时间复杂度为$O(min(n,m))$,最坏的时间复杂度为$O(max(n,m))$
3. 最少比较$min(n,m)$次，最多比较$m+n-1$次
4. 最好时的时间复杂度为$O(min(n,m))$,最坏的时间复杂度为$O(max(n,m))$

---

 

🎇这是一道结合线性表与时间复杂度的例题，可以顺带巩固之前的知识~🎇

如有错误，欢迎指正~！