📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 2975| 回复: 11
跳转到指定楼层
上一主题 下一主题
收起左侧

[Udacity CS215 Algorithm] 问个HW4计算中位数的题

全局:
公开课
学校名称: Udacity
Unit号: 4
开课时间: 2012-06-25
课程全名: CS215 Algorithms
平台: Udacity

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
普通解法,先给一个list排序,然后奇数就取中间那个,偶数就取中间两个的均值。# Your code should run in Theta(n) time

但是给list排序是theta(nlogn)不是吗? 题目要求是theta(n)计算中位数,咋实现的呢?
lecture里面说K order statistic,只要K不是跟n一个级别的,都可以跟min , max一样用theta(n)实现,这个我能理解。code也非常简单。
但是median is about n/2....


stanford的课里面说的是用两个heap,一个可以extract min, another can extract max,然后一个一个的examine 数字,分别放到两个heap,但是每个downheapify是theta(log i), i = 1, 2,3...n,加起来还不是nlogn么?


另外如果是random partition,每次把link随机分2部分,较长的部分里面再找下一个order statistic 虽然on average可以run in theta(n) time,但是是on average,不是总可以。。。。

求指教!

上一篇:Stanford CS106A 1#Assignment1讨论
下一篇:Stanford Design and Analysis of Algorithm I 第二期 Week#6 自由讨论
🔗
writecoffee1 2012-7-24 23:43:19 | 只看该作者
全局:
楼主您要参考TOPK的思路,找中位数时要randomly将L分解为(smaller, median, bigger),然后递归下去进行partition。同时注意median会有多个的情况

T(1) = 1
T(n) = N + 1/2 T(n/2) + 1/2 T(n)
WTN: T(n) = 4n
push through the equation: T(n) <= N + 1/2 * 2N + 2N = 4N = Theta(n)
回复

使用道具 举报

🔗
 楼主| modifiedname 2012-7-24 23:46:43 | 只看该作者
全局:
嗯,这个是我前面讲的random partition (可能叫法不准确?)on average可以实现theta(n)但是不能总保证。
比如特别寸,每次smaller, number, bigger里面只能去掉2个数字,剩余做递归的那一段是n-2,最后就是theta(n^2)的。。。
回复

使用道具 举报

🔗
writecoffee1 2012-7-25 00:05:09 | 只看该作者
全局:
小K 发表于 2012-7-24 23:46
嗯,这个是我前面讲的random partition (可能叫法不准确?)on average可以实现theta(n)但是不能总保证。
...

不是太懂,猜忘记了加入概率(1/2, 1/2) ?

这样算出来的确是upper bound~~
回复

使用道具 举报

🔗
 楼主| modifiedname 2012-7-25 00:11:15 | 只看该作者
全局:
ah? why 1/2??
回复

使用道具 举报

🔗
writecoffee1 2012-7-25 01:23:21 | 只看该作者
全局:
小K 发表于 2012-7-25 00:11
ah? why 1/2??

高中概率问题了,1/2的几率选择的pivot是前半段,这样算  T(n/2),1/2几率选择的pivot掉在后半段,这样算T(n)
回复

使用道具 举报

🔗
 楼主| modifiedname 2012-7-25 01:55:13 | 只看该作者
全局:
I know what you are saying for the "average" case...At any rate, it's not 1/2 but a fix percentage. As long as it's not 1/n, it can be derived for theta(n)

But the worst case will be theta(n^2)...isnt' it? -- or upper bound applies to the "upper bound on average"?

回复

使用道具 举报

🔗
writecoffee1 2012-7-26 02:48:04 | 只看该作者
全局:
本帖最后由 writecoffee1 于 2012-7-26 02:49 编辑
小K 发表于 2012-7-25 01:55
I know what you are saying for the "average" case...At any rate, it's not 1/2 but a fix percentage.  ...
高中概率问题了,1/2的几率选择的pivot是前半段,这样算  T(n/2),1/2几率选择的pivot掉在后半段,这样算T(n)

前半段这里算T(n/2)和后半段算T(n)(可以拿n-1放进去,但是为了简便,拿更worse的n放进去重新,相当于重新recurse了)已经是worse case了。

我猜如果拿1/n当概率算的话会更复杂,变成多项式求和了...

记得Tim Roughgarden讲master method时候quiz里有道概率题就是关于pivoting的。
回复

使用道具 举报

🔗
 楼主| modifiedname 2012-7-26 02:51:02 | 只看该作者
全局:
这个就跟quicksort差不多不?
http://en.wikipedia.org/wiki/Quicksort
回复

使用道具 举报

🔗
writecoffee1 2012-7-26 22:19:22 | 只看该作者
全局:
小K 发表于 2012-7-26 02:51
这个就跟quicksort差不多不?
http://en.wikipedia.org/wiki/Quicksort

worst case 的确是n square,看来蒙了~~~
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表