一亩三分地论坛

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

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

[树/链表/图] 谁给分析一下为什么树的前序遍历,空间复杂度是lgN?

[复制链接] |试试Instant~ |关注本帖
macrofun 发表于 2015-9-20 17:43:50 | 显示全部楼层 |阅读模式

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

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

x
自己数学不好这太吃亏了。对于分析时空复杂度的,有些能看懂,有些根本就是凭感觉。
比如这个,树的前序遍历,空间复杂度是lgN,是怎么分析出来的。
感谢大家的帮助。
zjuzqh 发表于 2015-9-20 18:44:20 | 显示全部楼层
你这里的lgN应该指的二叉树遍历的空间复杂度。空间复杂度记得是程序额外需占用的空间大小的度量,二叉树本身节点存储需要O(N)空间复杂度,二叉树前序遍历时需要额外的O(lgN)空间复杂度,用于栈空间。lgN是树高。
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-9-20 19:46:14 | 显示全部楼层
本帖最后由 robinho364 于 2015-9-20 19:47 编辑

这个和数学没有关系,和具体的算法有关系。
能不能把具体算法描述一下呢?

我的理解如果只是打印一下,根本不需要什么空间复杂度啊。。。。

如果是循环实现,那么需要开一个栈,在平衡二叉树的条件下,空间复杂度是O(log2(n))
如果是递归实现,空间复杂度是O(1)
回复 支持 反对

使用道具 举报

zjuzqh 发表于 2015-9-20 20:04:17 | 显示全部楼层
robinho364 发表于 2015-9-20 19:46
这个和数学没有关系,和具体的算法有关系。
能不能把具体算法描述一下呢?

你错了,递归方法是需要栈空间的。仍为O(lgN)。
回复 支持 反对

使用道具 举报

又见紫风铃 发表于 2015-9-20 20:21:38 | 显示全部楼层
robinho364 发表于 2015-9-20 19:46
这个和数学没有关系,和具体的算法有关系。
能不能把具体算法描述一下呢?

递归只是不是自己显式地写出栈,程序运行的时候要保存上一次递归结果是要压入内存的栈的
回复 支持 反对

使用道具 举报

 楼主| macrofun 发表于 2015-9-20 20:24:45 | 显示全部楼层
robinho364 发表于 2015-9-20 19:46
这个和数学没有关系,和具体的算法有关系。
能不能把具体算法描述一下呢?
  1. /**
  2. * Definition for a binary tree node.
  3. * struct TreeNode {
  4. *     int val;
  5. *     TreeNode *left;
  6. *     TreeNode *right;
  7. *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
  8. * };
  9. */
  10. class Solution {
  11. public:
  12.     bool isSameTree(TreeNode* p, TreeNode* q) {

  13.         stack<TreeNode*> myStack;
  14.         myStack.push(p);
  15.         myStack.push(q);
  16.       
  17.         while(!myStack.empty())
  18.         {
  19.             p = myStack.top();
  20.             myStack.pop();
  21.             q = myStack.top();
  22.             myStack.pop();
  23.             if(canSuccess(p,q))
  24.             {
  25.                 if(!p && !q)
  26.                     continue;
  27.                 if(p->val != q->val)
  28.                     return false;
  29.                 //采用先序遍历法 NLR   
  30.                 myStack.push(p->right);
  31.                 myStack.push(q->right);
  32.                 myStack.push(p->left);
  33.                 myStack.push(q->left);
  34.             }else{
  35.                 return false;
  36.             }
  37.         }
  38.         return true;
  39.     }
  40.    
  41.     bool canSuccess(TreeNode* p, TreeNode*q){
  42.         if(!p && !q)
  43.             return true;
  44.         else if(p && !q)
  45.             return false;
  46.         else if(!p && q)
  47.             return false;
  48.         else if(p->val != q->val)
  49.             return false;
  50.         
  51.         return true;
  52.     }
  53. };
复制代码
回复 支持 反对

使用道具 举报

stellari 发表于 2015-9-20 22:51:07 | 显示全部楼层
robinho364 发表于 2015-9-20 19:46
这个和数学没有关系,和具体的算法有关系。
能不能把具体算法描述一下呢?

这和具体的算法(除了Morris Traversal)还真没啥关系,无论迭代还是递归,都要至少用到O(logN)额外内存。不能因为我们看不到后者中栈空间的消耗情况,就说这时不存在内存消耗啊。
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-9-20 23:10:23 | 显示全部楼层
stellari 发表于 2015-9-20 22:51
这和具体的算法(除了Morris Traversal)还真没啥关系,无论迭代还是递归,都要至少用到O(logN)额外内存 ...

反对以上意见,所谓的程序内部的栈,和算法的栈没有关系。
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-9-20 23:15:56 | 显示全部楼层
robinho364 发表于 2015-9-20 23:10
反对以上意见,所谓的程序内部的栈,和算法的栈没有关系。

反对我自己的回答,根据wiki的解释:

https://en.wikipedia.org/wiki/DSPACE

It represents the total amount of memory space that a "normal" physical computer would need to solve a given computational problem with a given algorithm.

此外:

http://www.geeksforgeeks.org/g-fact-86/
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-9-20 23:16:25 | 显示全部楼层
zjuzqh 发表于 2015-9-20 20:04
你错了,递归方法是需要栈空间的。仍为O(lgN)。

我错了           
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-9-20 23:16:45 | 显示全部楼层
又见紫风铃 发表于 2015-9-20 20:21
递归只是不是自己显式地写出栈,程序运行的时候要保存上一次递归结果是要压入内存的栈的

嗯,我错了
回复 支持 反对

使用道具 举报

robinho364 发表于 2015-9-20 23:16:53 | 显示全部楼层
stellari 发表于 2015-9-20 22:51
这和具体的算法(除了Morris Traversal)还真没啥关系,无论迭代还是递归,都要至少用到O(logN)额外内存 ...

恩恩,我错了
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-5 03:40

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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