y*n
2 楼
randomized之后对于所有序列的时间复杂度期望都是n*lg(n).
i*o
3 楼
randomization is meant to reduce the possibility of occurrence of worst case
scenario.
worst case complexity is still n^n
【在 b*********n 的大作中提到】
: 仍旧是n^2吧，那randomized有啥用呢？仅仅为了已经排序的序列？
scenario.
worst case complexity is still n^n
【在 b*********n 的大作中提到】
: 仍旧是n^2吧，那randomized有啥用呢？仅仅为了已经排序的序列？
h*k
4 楼
对randomized 算法，讨论worst case意义不大，一般都是只看expected complexity
【在 b*********n 的大作中提到】
: 仍旧是n^2吧，那randomized有啥用呢？仅仅为了已经排序的序列？
【在 b*********n 的大作中提到】
: 仍旧是n^2吧，那randomized有啥用呢？仅仅为了已经排序的序列？
相关阅读
微软的背景调查有人面试过了fund accountant职位吗?background check能查出unpaid leave吗?One Programming/design question (Bloomberg FSE)金融/IT 面试体：概率如果fail了ebay onsite,多长时间可以重新拿到phone interview啊Google跟我要advisor的reference letter大家面试 带着自己的简历吗？一道面试题This is a contract, non-merit position within a pay-banding system下个礼拜人生第一个onsite，求bless并附部分phone interviewSoftware developer or tester job opportunity (转载)请问可以2个h1么？fulltime+partimeOPT 疑问请教一题请问前几天OPT加急收到BIOMETRICS通知的，你们收到了BIOMETRICS SCHEDULE DATE了吗？关于猎头的一个问题MSR 招 RSDE (转载)请问怎么谈packageH1B转F1保身份求推荐学校