在数据结构（严蔚敏）第二章课后习题中有这样一个题，关于把两个有序表合并的操作比较次数
将两个各有 N 个元素的有序表归并成一个有序表，其最少的比较次数是（ A）。
A.N
B.2N －1
C.2N
D.N －1
显然，比如A顺序表的最大值如果比B顺序表的最小值还要小，只需要拿B的最小元素与A中所有元素比较一遍即可，后续的B的所有元素都无需在比较。
在延伸一下，
将两个各有 N 个元素的有序表归并成一个有序表，其最多的比较次数是（ B）。
A.N
B.2N －1
C.2N
D.N －1
这种可以想象一下A顺序表，1，3，5......，B顺序表2，4，6......
恰好把B顺序表平均插入A顺序表中，如果B顺序表第二个元素不是4，而是6，那么B顺序表的最后一个元素就无需比较了，这样就少一个元素拿去比较，总的比较次数也就相应减少了。
如何计算比较次数呢？
B中的元素2要和A中的元素1和元素3比较两次，B中的元素4要和A中的元素3和元素5比较两次，4一定是比2大的，2之前的元素无需再比较，类比下去，B中的每一个元素都要比较两次（除了最后一个元素，最后一个元素只需比较一次就可以）总的次数=2（n-1）+1=2n-1.
奉上顺序表的删除和插入操作的平均时间复杂度怎么计算的
先看插入
如下面顺序表有七个元素
但是插入位置却有八个，从第1个位置（最前面）到第8个位置（最后面），那么插入每个位置的概率是相等的，就是1/8。有n个元素时，当在第一个位置插入时需要移动n个元素，第二个位置插入时需要移动n-1个元素，类比下去第i个位置插入时，需要移动n-i+1个元素，于是：
平均时间复杂度O（n）文章来源地址https://www.toymoban.com/news/detail-695693.html
再看删除
同样的，一个顺序表有7个元素，可删除的位置也就是7个，从第1个到第7个。
假如有n个元素，删除每一个元素的概率都相等，就是1/n；删除第一个元素时，需要移动的元素个数是6，删除第2个元素时，需要移动的元素个数是5，类比，删除第i个元素时需要移动的元素个数是n-i，于是有：
文章来源：https://www.toymoban.com/news/detail-695693.html
平均时间复杂度O（n）
到了这里，关于两个有序表合并成一个有序表最少与最多的比较次数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
