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

#2

世界模型2012-11-14 17:47

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

#3

寒风中的细雨2012-11-15 08:52

回复 2楼世界模型

3有空间限制么

#4

世界模型2012-11-15 12:15

回复 3楼寒风中的细雨

O(log2(n))

#5

寒风中的细雨2012-11-15 15:12

反向图调换一下结点的下标值不能解决么v1-->v2 v2-->v1

#6

寒风中的细雨2012-11-15 16:16

数组X             ------------------------------------  a
                                                        ^

数组Y             ------------------------------------  b
                                                        ^

a、b分别为两数字的最小值下标   假设排序是从小到大的

counter = 0; 计数器
a = 0;
b = 0;

while (counter < n)
{
    if (X[a] > X[b])
    {
       //丢弃b下标
       ++b;
    }
    else
    {
       //丢弃a下标
       ++a;
    }
    ++counter;//计数器+1
}

#7

寒风中的细雨2012-11-15 16:18

回复 6楼寒风中的细雨

6楼的时间复杂度 0(n)

如果需要达到 0(logn)的复杂度里面的计数器就需要换个增长方式

#8

寒风中的细雨2012-11-15 16:19

如果计数器的增长方式可以替换上： counter *= 2 时间复杂度就可以满足 0(logn)的要求

#9

寒风中的细雨2012-11-15 16:21

这里你可以借鉴下折半查找的思路去修改应该只要稍加修改就出来了

#10

世界模型2012-11-16 16:04

回复 9楼寒风中的细雨

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

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

#11

世界模型2012-11-16 16:15

回复 8楼寒风中的细雨

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

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

x=2*x;

程序代码：

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

斑竹能说明下不

#12

寒风中的细雨2012-11-16 16:33

回复 11楼世界模型

f(i) = 2 * i
f(i) < n
2 * i < n
i < logn

#13

世界模型2012-11-16 18:22

回复 12楼寒风中的细雨

这个我知道但不理解

#14

寒风中的细雨2012-11-16 19:02

回复 13楼世界模型

兄弟，自己加油了！！！

#15

世界模型2012-11-16 22:38

回复 14楼寒风中的细雨

奋斗中。。。

#16

世界模型2012-11-17 12:13

回复 12楼寒风中的细雨

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

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