(在归并排序中对小数组采用插入排序)虽然归并排序的最坏情况运行时间为,而插入排序的最坏情况时间为,但是插入排序中的常量因子可能使得它在n较小时,在许多机器上实际运行的更快。因此,在归并排序中当子问题变得足够小时,采用插入排序来使递归的页变粗是有意义的。考虑对归并排序的一中修改,其中使用插入排序来排序长度为k的n/k个子表,然后使用标准的合并机制来合并这些子表。这里k是一个待定的值: a.证明:插入排序最坏情况可以在时间内排序每个长度为k的n/k个子表。 b.表明在最坏情况下如何在时间内合并这些子表。 c.假定修改后的算法的最坏情况运行时间为时间内合并这些子表。 d.在实践中,我们应该如何选择k?-笔试面试资料

这是qklbishe.com第9392 篇笔试面试资料
提供答案分析,通过本文《(在归并排序中对小数组采用插入排序)虽然归并排序的最坏情况运行时间为,而插入排序的最坏情况时间为,但是插入排序中的常量因子可能使得它在n较小时,在许多机器上实际运行的更快。因此,在归并排序中当子问题变得足够小时,采用插入排序来使递归的页变粗是有意义的。考虑对归并排序的一中修改,其中使用插入排序来排序长度为k的n/k个子表,然后使用标准的合并机制来合并这些子表。这里k是一个待定的值: a.证明:插入排序最坏情况可以在时间内排序每个长度为k的n/k个子表。 b.表明在最坏情况下如何在时间内合并这些子表。 c.假定修改后的算法的最坏情况运行时间为时间内合并这些子表。 d.在实践中,我们应该如何选择k?-笔试面试资料》可以理解其中的代码原理,这是一篇很好的求职学习资料
本站提供程序员计算机面试经验学习,笔试经验,包括字节跳动/头条,腾讯,阿里,美团,滴滴出行,网易,百度,京东,小米,华为,微软等互联网大厂真题学习背诵。

答案:

(在归并排序中对小数组采用插入排序)虽然归并排序的最坏情况运行时间为(在归并排序中对小数组采用插入排序)虽然归并排序的最坏情况运行时间为,而插入排序的最坏情况时间为,但是插入排序中的常量因子可能使得它在n较小时,在许多机器上实际运行的更快。因此,在归并排序中当子问题变得足够小时,采用插入排序来使递归的页变粗是有意义的。考虑对归并排序的一中修改,其中使用插入排序来排序长度为k的n/k个子表,然后使用标准的合并机制来合并这些子表。这里k是一个待定的值:    a.证明:插入排序最坏情况可以在时间内排序每个长度为k的n/k个子表。    b.表明在最坏情况下如何在时间内合并这些子表。    c.假定修改后的算法的最坏情况运行时间为时间内合并这些子表。    d.在实践中,我们应该如何选择k?,而插入排序的最坏情况时间为(在归并排序中对小数组采用插入排序)虽然归并排序的最坏情况运行时间为,而插入排序的最坏情况时间为,但是插入排序中的常量因子可能使得它在n较小时,在许多机器上实际运行的更快。因此,在归并排序中当子问题变得足够小时,采用插入排序来使递归的页变粗是有意义的。考虑对归并排序的一中修改,其中使用插入排序来排序长度为k的n/k个子表,然后使用标准的合并机制来合并这些子表。这里k是一个待定的值:    a.证明:插入排序最坏情况可以在时间内排序每个长度为k的n/k个子表。    b.表明在最坏情况下如何在时间内合并这些子表。    c.假定修改后的算法的最坏情况运行时间为时间内合并这些子表。    d.在实践中,我们应该如何选择k?,但是插入排序中的常量因子可能使得它在n较小时,在许多机器上实际运行的更快。因此,在归并排序中当子问题变得足够小时,采用插入排序来使递归的页变粗是有意义的。考虑对归并排序的一中修改,其中使用插入排序来排序长度为k的n/k个子表,然后使用标准的合并机制来合并这些子表。这里k是一个待定的值:
a.证明:插入排序最坏情况可以在(在归并排序中对小数组采用插入排序)虽然归并排序的最坏情况运行时间为,而插入排序的最坏情况时间为,但是插入排序中的常量因子可能使得它在n较小时,在许多机器上实际运行的更快。因此,在归并排序中当子问题变得足够小时,采用插入排序来使递归的页变粗是有意义的。考虑对归并排序的一中修改,其中使用插入排序来排序长度为k的n/k个子表,然后使用标准的合并机制来合并这些子表。这里k是一个待定的值:    a.证明:插入排序最坏情况可以在时间内排序每个长度为k的n/k个子表。    b.表明在最坏情况下如何在时间内合并这些子表。    c.假定修改后的算法的最坏情况运行时间为时间内合并这些子表。    d.在实践中,我们应该如何选择k?时间内排序每个长度为k的n/k个子表。
b.表明在最坏情况下如何在(在归并排序中对小数组采用插入排序)虽然归并排序的最坏情况运行时间为,而插入排序的最坏情况时间为,但是插入排序中的常量因子可能使得它在n较小时,在许多机器上实际运行的更快。因此,在归并排序中当子问题变得足够小时,采用插入排序来使递归的页变粗是有意义的。考虑对归并排序的一中修改,其中使用插入排序来排序长度为k的n/k个子表,然后使用标准的合并机制来合并这些子表。这里k是一个待定的值:    a.证明:插入排序最坏情况可以在时间内排序每个长度为k的n/k个子表。    b.表明在最坏情况下如何在时间内合并这些子表。    c.假定修改后的算法的最坏情况运行时间为时间内合并这些子表。    d.在实践中,我们应该如何选择k?时间内合并这些子表。
c.假定修改后的算法的最坏情况运行时间为(在归并排序中对小数组采用插入排序)虽然归并排序的最坏情况运行时间为,而插入排序的最坏情况时间为,但是插入排序中的常量因子可能使得它在n较小时,在许多机器上实际运行的更快。因此,在归并排序中当子问题变得足够小时,采用插入排序来使递归的页变粗是有意义的。考虑对归并排序的一中修改,其中使用插入排序来排序长度为k的n/k个子表,然后使用标准的合并机制来合并这些子表。这里k是一个待定的值:    a.证明:插入排序最坏情况可以在时间内排序每个长度为k的n/k个子表。    b.表明在最坏情况下如何在时间内合并这些子表。    c.假定修改后的算法的最坏情况运行时间为时间内合并这些子表。    d.在实践中,我们应该如何选择k?时间内合并这些子表。
d.在实践中,我们应该如何选择k?
(在归并排序中对小数组采用插入排序)虽然归并排序的最坏情况运行时间为,而插入排序的最坏情况时间为,但是插入排序中的常量因子可能使得它在n较小时,在许多机器上实际运行的更快。因此,在归并排序中当子问题变得足够小时,采用插入排序来使递归的页变粗是有意义的。考虑对归并排序的一中修改,其中使用插入排序来排序长度为k的n/k个子表,然后使用标准的合并机制来合并这些子表。这里k是一个待定的值:    a.证明:插入排序最坏情况可以在时间内排序每个长度为k的n/k个子表。    b.表明在最坏情况下如何在时间内合并这些子表。    c.假定修改后的算法的最坏情况运行时间为时间内合并这些子表。    d.在实践中,我们应该如何选择k? 区块链毕设学生816410358号
a. 插入排序的时间在最坏的情况下为Θ(n^2)即每个插入排序需要k*k的时间,共用n/k个序列需要排序,故为 k*k* n/k = nk 即Θ(nk)。
b.和归并排序中的一样,每做一层排序需要n的时间,此时递归树的层高视为log(n/k)即为nlog(n/k);
c.Θ(nk+nlog(n/k)) = Θ(nk + nlogn – nlogk),可知归并排序为Θ(nlogn),当k=logn时,为Θ(2nlogn – nloglogn) 省略掉常数项和低阶后为Θ(nlogn);
d. 在实践中,我们应该选择k为最大值时的情况,即logn,以下观点不一定准确:我个人认为,本任务的前提是认为在数量较少的时候,插入排序比归并排序在机器上的表现更为优异,于是在上述c计算一样的情况下,选择最大值较为合理,从另一个方面来看,若k为越小越好,则k为1时和原本的归并排序并无不同。

今天 18:08:26 回复(0)

文章部分来自互联网,侵权联系删除
www.qklbishe.com

区块链毕设网(www.qklbishe.com)全网最靠谱的原创区块链毕设代做网站
部分资料来自网络,侵权联系删除!
资源收费仅为搬运整理打赏费用,用户自愿支付 !
qklbishe.com区块链毕设代做网专注|以太坊fabric-计算机|java|毕业设计|代做平台 » (在归并排序中对小数组采用插入排序)虽然归并排序的最坏情况运行时间为,而插入排序的最坏情况时间为,但是插入排序中的常量因子可能使得它在n较小时,在许多机器上实际运行的更快。因此,在归并排序中当子问题变得足够小时,采用插入排序来使递归的页变粗是有意义的。考虑对归并排序的一中修改,其中使用插入排序来排序长度为k的n/k个子表,然后使用标准的合并机制来合并这些子表。这里k是一个待定的值: a.证明:插入排序最坏情况可以在时间内排序每个长度为k的n/k个子表。 b.表明在最坏情况下如何在时间内合并这些子表。 c.假定修改后的算法的最坏情况运行时间为时间内合并这些子表。 d.在实践中,我们应该如何选择k?-笔试面试资料

提供最优质的资源集合

立即查看 了解详情