Time complexity - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

Time complexity

Time complexity# JobHunting - 待字闺中

d*o2012-02-04 08:02

1 楼

下面找lowestCommonAncestor的代码如果tree balance的话time complexity是多少？
自己想的不保险，请教一下。
我觉得是O(nlogn)
bool contain(node* root, node* cur)
{
if(root)
{
if(root==cur) return true;
return contain(root->left,cur)||contain(root->right,cur);
}
return false;
}
node* lowest(node* root, node* n1, node* n2)
{
if(root==n1||root==n2) return root;
if(root==NULL) return NULL;
bool isLeft1 = false;
bool isLeft2 = false;
if(root->left)
{
isLeft1 = contain(root->left,n1); //O(n)
isLeft2 = contain(root->left,n2);
}
if( isLeft1&&!isLeft2) return root;
if( !isLeft1&&isLeft2) return root;
if( isLeft1&&isLeft2) return lowest(root->left, n1, n2) ;
if(!isLeft1&&!isLeft2) return lowest(root->right, n1, n2);
}

r*t2012-02-04 08:02

2 楼

cracking 上面的第二个解法，不如最后那个好。

m*t2012-02-04 08:02

3 楼

天书

d*o2012-02-04 08:02

4 楼

啥意思？时间复杂度是多少？有人知道吗？

【在 m******t 的大作中提到】

: 天书

d*o2012-02-04 08:02

5 楼

书上也没有写时间复杂度。。。

【在 r****t 的大作中提到】

: cracking 上面的第二个解法，不如最后那个好。

H*e2012-02-04 08:02

6 楼

这题，contain这个函数是多余的,
整个nodes只要过一遍就好了 O(n)

【在 d****o 的大作中提到】

: 下面找lowestCommonAncestor的代码如果tree balance的话time complexity是多少？
: 自己想的不保险，请教一下。
: 我觉得是O(nlogn)
: bool contain(node* root, node* cur)
: {
: if(root)
: {
: if(root==cur) return true;
: return contain(root->left,cur)||contain(root->right,cur);
: }

d*o2012-02-04 08:02

7 楼

我这个代码是不是O(nlogn)?面试官问我。帮忙看看。
我看crack上面即使最后一个解法也需要O(nlogn)吧。
怎么能O(n)?除非你用多余空间吧。

【在 H***e 的大作中提到】

: 这题，contain这个函数是多余的,
: 整个nodes只要过一遍就好了 O(n)

H*e2012-02-04 08:02

8 楼

光从你这code看是O(n)啊,没仔细看你逻辑
T(n) = T(n/2) + O(n)

【在 d****o 的大作中提到】

: 我这个代码是不是O(nlogn)?面试官问我。帮忙看看。
: 我看crack上面即使最后一个解法也需要O(nlogn)吧。
: 怎么能O(n)?除非你用多余空间吧。

d*o2012-02-04 08:02

9 楼

刚刚去复习了一下主定理
好像是
T(n) = T(n/2) + n
a=1 b=2
n^(log2(1)) = 1
f(n)= n > 1
T(n) = O(n)
有意思哈。

【在 H***e 的大作中提到】

: 光从你这code看是O(n)啊,没仔细看你逻辑
: T(n) = T(n/2) + O(n)

H*e2012-02-04 08:02

10 楼

所以有时候你说面试官错的可能是你自己错喔

【在 d****o 的大作中提到】

: 刚刚去复习了一下主定理
: 好像是
: T(n) = T(n/2) + n
: a=1 b=2
: n^(log2(1)) = 1
: f(n)= n > 1
: T(n) = O(n)
: 有意思哈。

d*o2012-02-04 08:02

11 楼

上次那个我确定。。。
这次我知道没有复习主定理。
哪儿没有复习就问到哪儿。。。。

【在 H***e 的大作中提到】

: 所以有时候你说面试官错的可能是你自己错喔

w*z2012-02-04 08:02

12 楼

为什么呢？时间和空间复杂度都一样啊。

【在 r****t 的大作中提到】

: cracking 上面的第二个解法，不如最后那个好。

r*t2012-02-04 08:02

13 楼

这个按 master theorem 是 \Theta(nlogn) 说 O(nlogn) 没有错。

【在 d****o 的大作中提到】

: 刚刚去复习了一下主定理
: 好像是
: T(n) = T(n/2) + n
: a=1 b=2
: n^(log2(1)) = 1
: f(n)= n > 1
: T(n) = O(n)
: 有意思哈。

r*t2012-02-04 08:02

14 楼

常数项应该不同。

【在 w**z 的大作中提到】

: 为什么呢？时间和空间复杂度都一样啊。

h*n2012-02-04 08:02

15 楼

怎么得到T（n）= T(n/2)+n? 为什么不是T（n）= 2T(n/2) + 1
合并的复杂度为啥是n？求指教

h*n2012-02-04 08:02

16 楼

斗胆写了一个，请指教
复杂度：
T（n）= 2T（n/2）+ 1 复杂度为O（n）
TreeNode FindLowCommonNode(TreeNode root, TreeNode p, TreeNode q)
{
if(root==null || p == null || q == null)
return null;
if(root==p || root==q)
{
return root;
}
TreeNoe left = FindLowCommonNode(root.Left, p, q);
TreeNoe right = FindLowCommonNode(root.Right, p, q);
if(left!=null && right!=null)
{
return root;
}
return left==null? right:left;
}

d*o2012-02-04 08:02

17 楼

最后的4种情况，只有一种执行。

【在 h****n 的大作中提到】

: 怎么得到T（n）= T(n/2)+n? 为什么不是T（n）= 2T(n/2) + 1
: 合并的复杂度为啥是n？求指教

w*z2012-02-04 08:02

18 楼

see the structure below:
1
/ \
2 3
/
4
LCA of 4 and 3 should be 1. You program returns 4.
In then end, left is 4 and right is 3.

【在 h****n 的大作中提到】

: 斗胆写了一个，请指教
: 复杂度：
: T（n）= 2T（n/2）+ 1 复杂度为O（n）
: TreeNode FindLowCommonNode(TreeNode root, TreeNode p, TreeNode q)
: {
: if(root==null || p == null || q == null)
: return null;
: if(root==p || root==q)
: {
: return root;

h*n2012-02-04 08:02

19 楼

不会啊，你看我下面的分析：
TreeNode FindLowCommonNode(TreeNode root, TreeNode p, TreeNode q)
{
if(root==null || p == null || q == null)
return null;
if(root==p || root==q)
{
return root;
}
TreeNoe left = FindLowCommonNode(root.Left, p, q);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
这里left返回4
TreeNoe right = FindLowCommonNode(root.Right, p, q);
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
这里right返回3
if(left!=null && right!=null)
{
return root;
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
由于两个都不为null，这里直接返回root 1了
}
return left==null? right:left;
}

【在 w**z 的大作中提到】

: see the structure below:
: 1
: / \
: 2 3
: /
: 4
: LCA of 4 and 3 should be 1. You program returns 4.
: In then end, left is 4 and right is 3.

h*n2012-02-04 08:02

20 楼

就算这样子也应该为T（n ）= T(n/2) + 1, 最后怎么是为n，没看出来合并解需要n
求指教

【在 d****o 的大作中提到】

: 最后的4种情况，只有一种执行。

w*z2012-02-04 08:02

21 楼

好像是哦。我看错了

【在 h****n 的大作中提到】

: 不会啊，你看我下面的分析：
: TreeNode FindLowCommonNode(TreeNode root, TreeNode p, TreeNode q)
: {
: if(root==null || p == null || q == null)
: return null;
: if(root==p || root==q)
: {
: return root;
: }
: TreeNoe left = FindLowCommonNode(root.Left, p, q);

r*t2012-02-04 08:02

22 楼

也不太明白为啥是 +n 不是 +1...

【在 h****n 的大作中提到】

: 就算这样子也应该为T（n ）= T(n/2) + 1, 最后怎么是为n，没看出来合并解需要n
: 求指教

d*o2012-02-04 08:02

23 楼

因为contain是O(n)

【在 h****n 的大作中提到】

: 就算这样子也应该为T（n ）= T(n/2) + 1, 最后怎么是为n，没看出来合并解需要n
: 求指教