两个算法题半天没弄出个头绪大家看下 - 数据结构与算法

| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛 |

编程论坛 → 开发语言 → 『数据结构与算法』 → 两个算法题半天没弄出个头绪大家看下

我的收件箱(0)

欢迎加入我们，一同切磋技术

共有 897 人关注过本帖

标题：两个算法题半天没弄出个头绪大家看下

取消只看楼主加入收藏

世界模型

等　级：业余侠客
威　望：1
帖　子：240
专家分：226
注　册：2010-9-12
结帖率：97.44%

楼主

已结贴√ 问题点数：40 回复次数：7

两个算法题半天没弄出个头绪大家看下

图片附件: 游客没有浏览图片的权限，请登录或注册

4、T(n)=4T(n/4)+2T(n/4)+n T(n)=

2012-11-14 17:41

世界模型

等　级：业余侠客
威　望：1
帖　子：240
专家分：226
注　册：2010-9-12

第 2 楼

得分:0

PS：第四题写错了
T(n)=T(n/2)+T(n/4)+n T(n)=?

2012-11-14 17:47

世界模型

等　级：业余侠客
威　望：1
帖　子：240
专家分：226
注　册：2010-9-12

第 3 楼

得分:0

回复 3楼寒风中的细雨

O(log2(n))

2012-11-15 12:15

世界模型

等　级：业余侠客
威　望：1
帖　子：240
专家分：226
注　册：2010-9-12

第 4 楼

得分:0

回复 9楼寒风中的细雨

恩折半豁然开朗啊
思想:
设a、b为数组X、Y的中位数
1、a=b a或b即为所求
2、a<b 舍去X中较小的一半，同时舍去Y中较大的一半两次舍去长度相同
3、a>b 舍去X中较大的一半，同时舍去Y中较小的一半两次舍去长度相同

重复过程 1、2、3直到两个序列中均含一个元素为止较小者即为所求中位数

2012-11-16 16:04

世界模型

等　级：业余侠客
威　望：1
帖　子：240
专家分：226
注　册：2010-9-12

第 5 楼

得分:0

回复 8楼寒风中的细雨

通过增长方式求时间复杂度始终不是很理解
比如说：

x=2;
while(x<n/2)

 x=2*x;

程序代码：

void fun(int n)
{
   int i=1;
   while(i<=n)
      i=i*2;
}

斑竹能说明下不

2012-11-16 16:15

世界模型

等　级：业余侠客
威　望：1
帖　子：240
专家分：226
注　册：2010-9-12

第 6 楼

得分:0

回复 12楼寒风中的细雨

这个我知道但不理解

2012-11-16 18:22

世界模型

等　级：业余侠客
威　望：1
帖　子：240
专家分：226
注　册：2010-9-12

第 7 楼

得分:0

回复 14楼寒风中的细雨

奋斗中。。。

2012-11-16 22:38

世界模型

等　级：业余侠客
威　望：1
帖　子：240
专家分：226
注　册：2010-9-12

第 8 楼

得分:0

回复 12楼寒风中的细雨

为什么求复杂度的时候可以设 n=2^k

2012-11-17 12:13

快速回复：两个算法题半天没弄出个头绪大家看下