📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
查看: 1441| 回复: 4
跳转到指定楼层
上一主题 下一主题
收起左侧

[CareerCup] 问一下cc150 4.9的复杂度

🔗
MTC | 只看该作者 |倒序浏览
全局:

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

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
本帖最后由 MTC 于 2014-10-21 10:48 编辑

题目在这:
http://www.1point3acres.com/bbs/ ... 6orderby%3Ddateline

code:
  1. public static int depth(treeNode root){

  2. if(root==null){return 0;}

  3. else{
  4. return 1+Math.max(depth(root.left),depth(root.right));

  5. }

  6. }

  7. public static print(int[] path,int start,int end){

  8. for(int i=start;i<=end,i++){

  9. System.out.println(pathp[i]);

  10. }

  11. }

  12. public static findSum(treeNode root,int sum,int[] path,int level){

  13. if(root==null) return;

  14. path[level]=root.data;//put current node into path[]

  15. int t=0;

  16. /*search a path whose sum is sum,and current node is its end*/
  17. for(int i=level;i>=0;i++){

  18. t+=path[i];

  19. if(t==sum){

  20. print(path,i,level);

  21. }

  22. }

  23. findSum(root.left,path,level+1);
  24. findSum(root.right,path,level+1);

  25. }

  26. public static findSum(treeNode root,int sum){

  27. int depth=depth(root);

  28. int path[]=int[depth];

  29. findSum(root,sum,path,0);
  30. }
复制代码
这个遍历和preorder不是一样的吗?每个node走一次应该是O(N)啊,可是答案是n*logn,为啥啊?


【时间复杂度】
O(N^2) in worst case, O(NlgN) on average

【空间复杂度】
regardless of recursion depth, O(lgN) for node list to represent the path



上一篇:Return all amicable pairs less than given N
下一篇:算法超级大总结-- 面试中二叉树中常常考的题目欢迎讨论
🔗
pengds 2014-10-22 07:17:15 | 只看该作者
全局:
答案是说,在 n Level的每个节点都会被它上面的父节点访问一次,也就是总共n 次,
再加上所有的level ,就是一个等比数列乘等差数列,可以求和
回复

使用道具 举报

🔗
 楼主| MTC 2014-10-22 08:10:43 | 只看该作者
全局:
pengds 发表于 2014-10-22 07:17
答案是说,在 n Level的每个节点都会被它上面的父节点访问一次,也就是总共n 次,
再加上所有的level ,就 ...

n不是指节点的个数吗?怎么还能指某level的节点数?
回复

使用道具 举报

🔗
MCwong 2014-10-22 08:14:39 | 只看该作者
全局:
(1)父节点check的时间复杂度是O(n),因为每个节点都要check到.
(2)二叉搜索就是O(logn)的时间复杂度.
整个算法是在某一层每个点check所有的孩子,然后递归向深处搜索,所以时间复杂度应该是O(nlogn).
回复

使用道具 举报

🔗
pengds 2014-10-22 08:26:49 | 只看该作者
全局:
MTC 发表于 2014-10-22 08:10
n不是指节点的个数吗?怎么还能指某level的节点数?

在N层有2^n 个节点,每个节点被check n 次
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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