夜猫酱 发表于 2011-5-16 21:05:59

一个程序的时间复杂度问题 （数据结构）

unsigned long int f(unsigned long int x)
{
if(1 == x )return 1;
if(3 == x ) return 3;
if(x%2 == 0) return f(x/2);
if(x%4 == 1) return 2*f((x+1)/2)-f((x-1)/4);
return 3*f((x-1)/2)-2*f((x-3)/4);

}
void main()
{
unsigned long int num = 0 ;
for(unsigned long int i = 1; i<=46950383;i ++)
{
if(i == f(i))
num++;
}
printf("%d ",num);

}




if(i == f(i))



用了递归的判断   求时间复杂度。

JEVJEL 发表于 2011-5-17 00:20:46

学习学习学习

JEVJEL 发表于 2011-5-17 00:40:50

学习学习学习

仰望天上的光 发表于 2011-5-22 16:32:50

假设函数f对于输入n的时间复杂度是f(n),有：
f(n)=f(n/2)               n%2 == 0
f(n)=f(n/2)+f(n/4)    x%4 == 1
f(n)=f(n/2)+f(n/4)    其它

显然，f(n)=f(n/2) 收敛慢，f(n)=f(n/4)收敛快。又每种情况都需要计算f(n/2)所以f(n)时间复杂度是O(logN).而且是以2为底的log

zxyuan 发表于 2011-5-25 09:45:53

复杂.学习学习

旭日东升 发表于 2011-5-25 16:51:20

{:soso__3677294909454784722_1:}

夜猫酱 发表于 2011-5-25 17:35:02

旭日东升 发表于 2011-5-25 16:51 static/image/common/back.gif


东升~~~肿么了~~~

嗜血丨灵异狂 发表于 2011-5-26 05:42:24

绝对菜鸟学习中 孜孜不倦

dps521 发表于 2015-11-28 11:20:36

:smile:smile:smile:smile
页: [1]
查看完整版本: 一个程序的时间复杂度问题 （数据结构）