试题-对于以下说法，错误的是（）。

题目

对于以下说法，错误的是（）。

A.Dijkstra算法用于求解图中两点间最短路径，其时间复杂度O(n^2)

B.Floyd-Warshall算法用于求解图中所有点对之间最短路径，其时间复杂度为O(n^3)

C.找出n个数字的中位数至少需要O(n*logn)的时间

D.基于比较的排序问题的时间复杂度下界是O(n*logn)

解答

正确答案是 C

AB正确，考察基本算法。D正确，基于比较的话，怎么样都至少需要O(n*logn)的时间。找一个数是否是中位数，可以利用快排的过程（而不是快排），就和O(N)第K数一样。C.利用顺序统计思路找出n个数字的中位数可以再O(n)时间内完成，所以C错误。

C 4条回复评论

毛大军

用快速排序的方法，可以使时间复杂度为O（n）

发表于 2018-10-13 16:00:33

柠檬很甜

D说的是平均复杂度

发表于 2018-10-13 16:00:19

星辰大海

基于比较的排序时间复杂度用直接插入最优情况不是O(n)吗，那么d中下界应该是o(n)吧

发表于 2018-10-13 16:00:13

寒山远火

不过对于A而言， Dijkstra求解图最短路径的复杂度与所选的数据结构有关，如果用数组，则为O(n^2)，若选用二叉堆，则为O(elogn)，若选用Fibonacci堆，则为O(e+nlogn)，所以个人感觉A的说法也不准确。

发表于 2018-10-13 16:00:07