| 查看: 1375 | 回复: 6 | |||
[求助]
【求助】一道算法题目
|
|
题目如图 本人在国外一所大学读书，由于英文不咋地，导致题目都没有看懂，悲催啊，求大神指点 另：如何判断f=Θ(g)?例如：f(n)=nlogn,g(n)=10nlog10n 跪求指点啊。。。  题目 [ Last edited by mca088 on 2012-8-28 at 05:07 ] |
回复此楼» 猜你喜欢
今天系统多次维护，明天很可能放榜！
已经有5人回复
-
欢迎发来filecode的Mz6后的代码验证其规律
已经有74人回复
-
岩土工程学报什么时候才能终审完呐
已经有4人回复
-
时间戳又变了8-15
已经有25人回复
-
2027广东省杰青
已经有6人回复
-
快农历七夕节了，轻松一下，男人悄悄话，女施主请不要进来。
已经有3人回复
-
哪位老哥知道今年的国自然具体哪一天放榜？
已经有9人回复
-
咱们一起用铁证分析2026国家社科基金中标与否
已经有26人回复
-
我的国基提前知道中了，可是同事的操作让我实在接受不了，怎么会有这样的人
已经有16人回复
-
有时候，自然基金真的不能太认真 （我的申报经验）
已经有12人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 数字信号处理的一道题目，大家帮忙！
已经有6人回复
- Euler Project Q13 欧拉工程第十三题
已经有20人回复
youth0826
至尊木虫 (著名写手)
weibo.com/138147022
- 应助: 172 (高中生)
- 金币: 10458.4
- 散金: 145
- 红花: 4
- 帖子: 1726
- 在线: 149.4小时
- 虫号: 707170
- 注册: 2009-02-23
- 专业: 模式识别
【答案】应助回帖
★ ★ ★ ★ ★
感谢参与，应助指数 +1
mca088: 金币+5, ★★★很有帮助 2012-08-29 14:33:14
感谢参与，应助指数 +1
mca088: 金币+5, ★★★很有帮助 2012-08-29 14:33:14
|
算法题？英文倒是简单哦 E是一个整数的序列，含有n个整数，可以有相同的整数，如果某个整数出现的次数，大于一半，比如n=10，其中整数k出现了6次（>10/2），就可以说的大多数（majority）。 问题a限定了每个整数数值的范围，必须在[1,r]之间，要设计一个时间O（n+r）内的算法判定某个序列E有没有majority。 问题b，c，d没有数值范围限定。 问题b要求在时间O(nlogn)内判定E有没有majority。 问题c，假设序列E有majority，是k，给定序列中两个不等的数，证明，去掉这两个数之后的序列仍有majority是k。 问题d，利用c的结果，将b算法改进，让时间从O(nlogn)到O(n)。。。 自己做题去吧。。。哎 |
2楼2012-08-28 08:48:08
rockinuk
铁杆木虫 (职业作家)
- 应助: 1512 (讲师)
- 金币: 7810.9
- 散金: 189
- 红花: 106
- 帖子: 3982
- 在线: 570.6小时
- 虫号: 1945379
- 注册: 2012-08-19
- 性别: GG
- 专业: 数论
3楼2012-08-28 09:28:21
pgc201106
木虫 (正式写手)
专业码农
- 应助: 2 (幼儿园)
- 金币: 3005.6
- 帖子: 521
- 在线: 111.1小时
- 虫号: 727178
- 注册: 2009-03-20
- 性别: GG
- 专业: 计算机网络
4楼2012-08-28 09:40:01
5楼2012-08-28 20:50:28
6楼2012-08-28 20:51:48
youth0826
至尊木虫 (著名写手)
weibo.com/138147022
- 应助: 172 (高中生)
- 金币: 10458.4
- 散金: 145
- 红花: 4
- 帖子: 1726
- 在线: 149.4小时
- 虫号: 707170
- 注册: 2009-02-23
- 专业: 模式识别
7楼2012-08-29 09:37:21
25
