| 查看: 1076 | 回复: 6 | ||
[求助]
【求助】一道算法题目
|
|
题目如图 本人在国外一所大学读书，由于英文不咋地，导致题目都没有看懂，悲催啊，求大神指点 另：如何判断f=Θ(g)?例如：f(n)=nlogn,g(n)=10nlog10n 跪求指点啊。。。  题目 [ Last edited by mca088 on 2012-8-28 at 05:07 ] |
回复此楼» 猜你喜欢
290求调剂
已经有9人回复
-
321求调剂
已经有4人回复
-
326求调剂
已经有5人回复
-
东南大学364求调剂
已经有4人回复
-
085600材料与化工 求调剂
已经有13人回复
-
一志愿985，本科211，0817化学工程与技术319求调剂
已经有4人回复
-
311求调剂
已经有6人回复
-
0703化学调剂 290分有科研经历，论文在投
已经有4人回复
-
化学工程321分求调剂
已经有6人回复
-
本人考085602 化学工程 专硕
已经有9人回复
» 本主题相关价值贴推荐，对您同样有帮助:
- 数字信号处理的一道题目，大家帮忙！
已经有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
20