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

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

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

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

登录/注册后可看大图

东升~~~肿么了~~~

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

绝对菜鸟学习中孜孜不倦

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

:smile:smile:smile:smile

账号		自动登录	找回密码
密码			立即注册

[争议讨论] 一个程序的时间复杂度问题 （数据结构）

马上注册，结交更多好友，享用更多功能^_^

[争议讨论] 一个程序的时间复杂度问题（数据结构）