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有啥用呢？仅仅为了已经排序的序列？
相关阅读
公司挂opt被举报该怎么办Re: 实在不知道我的老板是不是傻逼 还是我傻逼 (转载)求问版上有谁做过citigroup的background check，请教流程oracle job opportunitesgoogle 不是面经的面经最近公司职位挺多，有需要refer的吱一声呀G家面经（已被HC挂，求分析）leetcode服务器又down了，咱能不说名字的事儿了不事不宜迟：如何舆论矛头往烙印身上引 (转载)查工资水平的网站求推荐剑走偏锋：地铁十八摸吸引北美高端人才回流被狗家店面据的莫名其妙，发个面经吧Kleiner Perkins 烙印男性骚扰华女上法庭 (转载)求指导。amazon电面通知。接不接得住？封杀掉一个烙印狗狗瑞库特不耐烦了CS不奢望大公司,求小公司refer实习或工作,会答谢一个月工资Linkedin有题库吗？关于找工作时面试官的last namesurvey Monkey和service now比较