归并排序的时间复杂性是 ( )
举一反三
- 在归并排序中，归并排序算法的时间复杂性为______。
- 时间复杂性为O(nlog2n)且空间复杂性为O(1)的排序方法是( )。 A: 归并排序 B: 堆排序 C: 快速排序 D: 锦标赛排序
- 下面那个算法在最坏情况下的时间复杂性最低 A: 归并排序 B: 插入排序 C: 快速排序 D: 冒泡排序
- 简述二路归并排序,并分析其算法复杂性.
- 快速排序和归并排序是常用的排序算法，也都是采用分治法解决的问题。快速排序的时间复杂性为O(n2), 而归并排序的时间复杂性为O(nlogn), 究其原因，下面的解释你认为哪个正确？（ ） A: 这是因为归并排序把问题划分为子问题时的时间复杂性低，而快速排序划分为子问题是使用partition()函数，划分为子问题的时间复杂性高。 B: 归并排序的分和合的时间复杂性之和低于快速排序的分和合的时间复杂性之和。 C: 因为归并排序把问题划分为两个子问题时其规模大致相等，是原来规模的n/2，而快速排序划分为子问题是使用partition()函数，划分为子问题时不能保证二个子问题的规模大致相同，在极端状况下，每次都只划分为1个子问题，其规模为n-1，因此快速排序在极端状况下的时间复杂性的递归定义为T(n)=T(n-1)+O(n)。 D: 以上都不正确。