l******4
发帖数: 729 | 1 对方真是nice阿。
问的题都不难，可惜我本人努力不够。
连quick sort具体问题都没答出。
我本科不是学CS的，Master才转过来。 确实感觉很多细节不如cs本可出身的扎实。
人家问in the worst case, how to improve quick sort so that it is not O(n2).
人家启发了我半天，我还是没答出。
一共问了6个题，一个不会，一个在人家提示下答出。 本应45分钟，结果40分钟就结束了。人家不待见我......
你们鄙视我吧。 |
r****o
发帖数: 1950 | 2 Quicksort的那个题目是不是应该说每次partition的时候随机选择一个元素跟最后一个
互换？对吗？
束了。人家不待见我......
【在 l******4 的大作中提到】
: 对方真是nice阿。
: 问的题都不难，可惜我本人努力不够。
: 连quick sort具体问题都没答出。
: 我本科不是学CS的，Master才转过来。 确实感觉很多细节不如cs本可出身的扎实。
: 人家问in the worst case, how to improve quick sort so that it is not O(n2).
: 人家启发了我半天，我还是没答出。
: 一共问了6个题，一个不会，一个在人家提示下答出。 本应45分钟，结果40分钟就结束了。人家不待见我......
: 你们鄙视我吧。
|
s*********g
发帖数: 849 | 3 为啥不问我这个。sigh
O(n2).
束了。人家不待
见我......
【在 l******4 的大作中提到】
: 对方真是nice阿。
: 问的题都不难，可惜我本人努力不够。
: 连quick sort具体问题都没答出。
: 我本科不是学CS的，Master才转过来。 确实感觉很多细节不如cs本可出身的扎实。
: 人家问in the worst case, how to improve quick sort so that it is not O(n2).
: 人家启发了我半天，我还是没答出。
: 一共问了6个题，一个不会，一个在人家提示下答出。 本应45分钟，结果40分钟就结束了。人家不待见我......
: 你们鄙视我吧。
|
S******A
发帖数: 1002 | 4 worst case, already sorted, always pick first or last elem as pivot bah?
randomly pick pivot |
h*******x
发帖数: 12808 | 5 没事，据说bloomberg今年有好多opening，能招收几百个intern和fulltime
束了。人家不待见我......
【在 l******4 的大作中提到】
: 对方真是nice阿。
: 问的题都不难，可惜我本人努力不够。
: 连quick sort具体问题都没答出。
: 我本科不是学CS的，Master才转过来。 确实感觉很多细节不如cs本可出身的扎实。
: 人家问in the worst case, how to improve quick sort so that it is not O(n2).
: 人家启发了我半天，我还是没答出。
: 一共问了6个题，一个不会，一个在人家提示下答出。 本应45分钟，结果40分钟就结束了。人家不待见我......
: 你们鄙视我吧。
|
f****4
发帖数: 1359 | 6 汗，要是让我写quick sort，估计也玄
都是直接用sort的。。。 |
f****4
发帖数: 1359 | |
k***e
发帖数: 556 | 8 check the textbook introduction to algorithms
there are several choices
1) permute the whole array before sorting
2) choose partition element as the median of 3 randomly chosen indexes
【在 S******A 的大作中提到】
: worst case, already sorted, always pick first or last elem as pivot bah?
: randomly pick pivot
|
l***i
发帖数: 1309 | 9 krone's solution is incorrect.
To get worst case O(nlogn) you need to get the exact median of the array in
linear time, then use it as pivot. |
f**r
发帖数: 865 | 10 comfort~ 应付面试的话，这些基本的算法还是该多复习一下的。我曾经有一次面试卡
在了heap sort上，回去以后后悔死了，呵呵。 |
|
|
k***e
发帖数: 556 | 11 i did not say we can assure to get nlgn with this
i just mean we can improve the probability of getting better performance
btw, if you use linear selection algorithm, which is recursive solution, you
have to take take space used on the stack and you also need at least a n/5
size array to store the medians you obtained.
in
【在 l***i 的大作中提到】
: krone's solution is incorrect.
: To get worst case O(nlogn) you need to get the exact median of the array in
: linear time, then use it as pivot.
|
m****u
发帖数: 3915 | 12 不对吧，不管逆序顺序，都慢
无序才快
【在 h*******x 的大作中提到】
: 没事，据说bloomberg今年有好多opening，能招收几百个intern和fulltime
:
: 束了。人家不待见我......
|
m****u
发帖数: 3915 | 13 楼主能不能把其他几道题也贡献出来？谢谢了
O(n2).
束了。人家不待
见我......
【在 l******4 的大作中提到】
: 对方真是nice阿。
: 问的题都不难，可惜我本人努力不够。
: 连quick sort具体问题都没答出。
: 我本科不是学CS的，Master才转过来。 确实感觉很多细节不如cs本可出身的扎实。
: 人家问in the worst case, how to improve quick sort so that it is not O(n2).
: 人家启发了我半天，我还是没答出。
: 一共问了6个题，一个不会，一个在人家提示下答出。 本应45分钟，结果40分钟就结束了。人家不待见我......
: 你们鄙视我吧。
|
h*******x
发帖数: 12808 | 14 恩，我糊涂了。
【在 m****u 的大作中提到】
: 不对吧，不管逆序顺序，都慢
: 无序才快
|
r****o
发帖数: 1950 | 15 CLRS里面关于Qsort的伪代码提到了在partition之前先取一随机元素和最后一个元素互
换，
如果Qsort是这样实现的话，是不是就跟逆序顺序无序没啥关系了?
【在 m****u 的大作中提到】
: 不对吧，不管逆序顺序，都慢
: 无序才快
|
m****u
发帖数: 3915 | 16 恩，那就是随机选pivot
【在 r****o 的大作中提到】
: CLRS里面关于Qsort的伪代码提到了在partition之前先取一随机元素和最后一个元素互
: 换，
: 如果Qsort是这样实现的话，是不是就跟逆序顺序无序没啥关系了?
|
w******1
发帖数: 520 | 17 数据结构的书上有优化算法， 就是取中间值。避免N^2 |
