分析分治合并排序算法的时间复杂性。
题目
相似考题
更多“分析分治合并排序算法的时间复杂性。”相关问题
-
第1题：
对于具有n个元素的一个数据序列，若只需得到其中第k个元素之前的部分排序，最好采用(59)，使用分治(Divide and Conquer)策略的是(60)算法。
A．希尔排序
B．直接插入排序
C．快速排序
D．堆排序
正确答案：D
解析：本题考查排序算法及特点。对于希尔排序、直接插入排序，只有在排序过程后才能确保全部序列以及前k个元素的最终排列，快速排序采用分治算法，常用递归算法实现，该算法根据枢轴元素进行划分，第一趟划分结束后得到了两个子序列，一个序列中的元素均不大于另一个子序列中的元素，枢轴元素介于这两个子序列之间。若仅需得到最终序列的前k个元素，每次得到枢轴元素位置后再考虑下一步的排序过程，在算法的流程控制上比较复杂。对于只需得到最终序列的前k个元素，堆排序比较简单。 -
第2题：
归并排序采用的算法设计方法属于( )。
A．归纳法
B．分治法
C．贪心法
D．回溯方法
正确答案：B
解析：以2一路归并排序为例进行说明。2一路归并是指将两个有序序列合并成一个有序序列，其基本过程为；从两个序列中各取一个元素，进行比较，输出较小的元素，从较小元素所在序列取下一个元素，与未输出的那个元素比较，输出较小者。依此类推，直到输出序列包含了两个初始有序序列的全部元索。对于一个初始无序的序列，可以先将其等分为两个无序的子序列，对这两个子序列再次二分，重复该过程，直到分出的子序列中仅包含一个元素时(一个元素自然是有序的)为止，然后在反复进行2一路归并的过程，最后完成排序。 -
第3题：
计算冒泡排序算法时间复杂性的阶。参考答案：计算冒泡排序算法时间复杂度
冒泡排序的主要步骤：
for i=1 to n-1 do
for j=1 to n-i do
if a[j]>a[j+1] then交换a[j]，a[j+1];
用比较次数作为算法的计量，比较一次所花的时间为常数，用O(1)表示，内循环所花时间ΣO(1)=O(n-i)，外循环所花时间：ΣO(n-i)=O(n(n-1)/2)=O(n²)
-
第4题：
分治合并排序的是怎样分治的参考答案：if问题不可分then求解
else{m=(p+q)/2;
对a[p,m]排序;
对a[m+1，q]排序;
将a[p,m]和a[m+1，q]合并;
}
-
第5题：
分治合并排序的二分归并过程在最好情况下花费多少时间参考答案：最好情况下需比较n/2次。
-
第6题：
快速排序算法采用的设计方法是______。
A．动态规划法
B．分治法
C．回溯法
D．分枝定界法
A．
B．
C．
D．
正确答案：B
-
第7题：
实现合并排序利用的算法是（）。
- A、分治策略
- B、动态规划法
- C、贪心法
- D、回溯法
正确答案:A -
第8题：
算法分析的目的是（），算法分析的两个主要方面是（）。
- A、找出数据结构的合理性
- B、研究算法中的输入和输出关系
- C、分析算法的效率以求改进
- D、分析算法的易懂性和文档性
- E、空间复杂度和时间复杂度
- F、正确性和简明性
- G、可读性和文档性
- H、数据复杂性和程序复杂性
正确答案:C,E -
第9题：
合并排序算法是利用（）实现的算法。
- A、分治策略
- B、动态规划法
- C、贪心法
- D、回溯法
正确答案:A -
第10题：
关于算法的时间复杂性，下列叙述正确的是（）。
- A、时间复杂性是衡量一个算法优劣的唯一标准
- B、所有算法都与问题的规模有关，问题规模越大，时间复杂性越大
- C、通常不能简单地以算法运行时间度量算法的时间复杂性
- D、同一个算法可以编写为不同的程序，程序的执行时间不同，因此一个算法有多种不同的时间复杂性
正确答案:C -
第11题：
问答题简述归并排序算法和快速排序算法的分治方法。正确答案： 1）归并排序的分治是将数组从中间分开，分别对前后来那个部分进行排序，将排序后的两个数组合并成整个数组的排序。这样分治为递归过程，直到一个元素时返回。
2）快速排序的分治是选取分割元素，以分割元素为界，将数组分成两部分，一部分小于分割元素，一部分大于分割元素，分别对两部分排序。解析： 暂无解析 -
第12题：
单选题实现合并排序利用的算法是（）。A分治策略
B动态规划法
C贪心法
D回溯法
正确答案： D解析： 暂无解析 -
第13题：
以下关于快速排序算法的描述中，错误的是( )。在快速排序过程中，需要设立基准元素并划分序列来进行排序。若序列由元素{12，25，30，45，52，67，85}构成，则初始排列为( )时，排序效率最高(令序列的第一个元素为基准元素)。
A．快速排序算法是不稳定的排序算法
B．快速排序算法在最坏情况下的时间复杂度为0(nlgn)
C．快速排序算法是一种分治算法
D．当输入数据基本有序时，快速排序算法具有最坏情况下的时间复杂度
正确答案：B
解析：最坏情况是每次划分选取的基准都是当前无序区中关键字最小(或最大)的记录，划分的结果是基准左边的子区间为空(或右边的子区间为空)，而划分所得的另一个非空的子区间中记录数目，仅仅比划分前的无序区中记录个数减少一个。因此，快速排序必须做n-1次划分，第i次划分开始时区间长度为n-i+1，所需的比较次数为n-i(1≤i≤n-1)，故总的比较次数达到最大值：cmax=n(n-1)／2=O(2)在最好情况下，每次划分所取的基准都是当前无序区的“中值”记录，划分的结果是基准的左、右两个无序子区间的长度大致相等。总的关键字比较次数：O(nlgn) -
第14题：
分析maxmin算法的时间复杂性。参考答案：
-
第15题：
分析汉诺塔算法的时间复杂性。参考答案：
-
第16题：
快速排序算法的最坏时间复杂性和平均时间复杂性函数。参考答案：快速排序算法的最坏情况下的时间复杂性的阶为O(n²)，其原因是a[p：j-1]和a[j+1：q]的大小不是均衡的。快速排序算法的平均时间复杂性的阶为O(nlogn)。
-
第17题：
算法的复杂性分析主要是分析算法的什么耗费情况?参考答案：算法的复杂性是算法运行所需要的计算机资源的耗费量，需要的时间资源的耗费量称作时间复杂性。
-
第18题：
快速排序算法在排序过程中，在待排序数组中确定一个元素为基准元素，根据基准元素把待排序数组划分成两个部分，前面一部分元素值小于等于基准元素，而后面一部分元素值大于基准元素。然后再分别对前后两个部分进一步进行划分。根据上述描述，快速排序算法采用了 (61) 算法设计策略。已知确定基准元素操作的时间复杂度为
，则快速排序算法的最好和最坏情况下的时间复杂度为 (62) 。A.分治
B.动态规划
C.贪心
D.回溯
正确答案：A
本题考查快速排序算法。快速排序算法是应用最为广泛的排序算法之一。其基本思想是将n个元素划分为两个部分：一部分元素值小于某个数；另一部分元素值大于某个数，该数的位置确定；然后进一步划分前面部分和后面部分。根据该叙述，可以知道，这里采用的是分治算法设计策略。由于已知划分操作的时间复杂度为，不需要合并子问题的答案。对于最好的情况，应该是每次划分都把n个元素划分为大约2个n/2个元素的子数组，此时T(n)=2T(n/2)+解该递归式，可得时间复杂度为。若刚好划分的极度不均衡，即每个划分刚好把n个元素划分为一边0个元素，一边n-l个元素，此时T(n)=T(n/1)+解该递归式，可得时间复杂度为。 -
第19题：
简述归并排序算法和快速排序算法的分治方法。
正确答案: 1）归并排序的分治是将数组从中间分开，分别对前后来那个部分进行排序，将排序后的两个数组合并成整个数组的排序。这样分治为递归过程，直到一个元素时返回。
2）快速排序的分治是选取分割元素，以分割元素为界，将数组分成两部分，一部分小于分割元素，一部分大于分割元素，分别对两部分排序。 -
第20题：
分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是冒泡算法，最费时间的是（）算法。
正确答案:快速 -
第21题：
算法的时间复杂性越好，可读性就越差；反之，算法的可读性越好，则时间复杂性就越差。
正确答案:错误 -
第22题：
单选题合并排序算法是利用（）实现的算法。A分治策略
B动态规划法
C贪心法
D回溯法
正确答案： C解析： 暂无解析 -
第23题：
单选题以下常用算法中，适合计算等差级数的算法是（）A分治法
B排序法
C枚举法
D递推法
正确答案： C解析： 暂无解析