2. 计算机
  3. 快速排序是一种典型的分治算法。采用快速排序对数组A[p．．r]排序的三个步骤如下： 分解：选择一个枢轴

快速排序是一种典型的分治算法。采用快速排序对数组A[p．．r]排序的三个步骤如下： 分解：选择一个枢轴

admin2015-06-03  82
问题 快速排序是一种典型的分治算法。采用快速排序对数组A[p．．r]排序的三个步骤如下：
    分解：选择一个枢轴    递归求解：通过递归的调用快速排序，对子数组A[p．．q-1]和A[q+1．．r]分别排序。
    合并：快速排序在原地排序，故不需合并操作。
(1)假设要排序包含n个元素的数组，请给出在各种不同的划分情况下，快速排序的时间复杂度，用O记号。最佳情况为(4)，平均情况为(5)，最坏情况为(6)。
    (2)假设要排序的n个元素都具有相同值时，快速排序的运行时间复杂度属于哪种情况?(7)。(最佳、平均、最坏)
选项
答案(4)O(nlgn)或O(nlog2n)。 (5)O(nlgn)或O(nlog2n)。 (6)O(n2)。 (7)最坏。
解析
转载请注明原文地址:https://kaotiyun.com/show/QdDZ777K
本试题收录于： 软件设计师下午应用技术考试题库软考中级分类
0

软件设计师下午应用技术考试

软考中级

相关试题推荐
随机试题
最新回复(0)