一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 369|回复: 2
收起左侧

[算法题] 求分一个recursive function的复杂度

[复制链接] |试试Instant~ |关注本帖
gjy 发表于 2015-1-8 09:14:51 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
请问f(x)的复杂是多少?
int f(int x){
if (x<1) return 1;
else return f(x-1)+g(x);
}
int g(int x){
if (x<2) return 2;
else return f(x-1)+g(x/2);
}

zj45499 发表于 2015-1-8 12:55:37 | 显示全部楼层
本帖最后由 zj45499 于 2015-1-8 13:06 编辑

First rewrite g in terms of f. You get:
  1.     static int g1(int x) {
  2.         if (x < 2) {
  3.             return 2;
  4.         } else {
  5.             return f(x - 1) + f(x/2) -f(x/2-1);
  6.         }
  7.     }
复制代码
Then rewrite f in terms if f. You get:
  1.     static int f1(int x) {
  2.         if (x < 1) {
  3.             return 1;
  4.         } else {
  5.             return 2 * f(x-1) +f(x/2)-f(x/2-1);
  6.         }
  7.     }
复制代码
To calculate a given n, you have to spent twice the time spent on (n-1). This is O(2^n).
the time complexity of f(x / 2) and f(x / 2 - 1) is O(log n).
So O(f(n)) = O(2^n) + O(log n), Or simply O(2^n).


In my machine,
f(19) ~ 3 ms
f(20) ~ 6 ms
f(21) ~ 11 ms
f(22) ~ 23 ms
f(23) ~ 45 ms
f(24) ~ 92 ms
f(25) ~ 186 ms
f(26) ~ 370 ms
f(27) ~ 756 ms
f(28) ~ 1479 ms
f(29) ~ 2952 ms
f(30) ~ 5862 ms
f(31) ~ 12001 ms
...
f(99) ~ STILL RUNNING, should take about 2*10^14 yrs.

This is much too slow.
回复 支持 反对

使用道具 举报

 楼主| gjy 发表于 2015-1-9 03:36:33 | 显示全部楼层
真精准!大赞
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-7 04:18

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表