[理工] 资结 tree gary19941208 PTT批踢踢实业坊

楼主: gary19941208 2016-11-23 11:01:38

http://i.imgur.com/sqQqgqq.jpg
请问D选项正确答案应该是O(log(max(n_a,n_b)+1))吗？
如果是的话想问O(logn)和O(log(n+1))不一样吗？

作者: hopward (hopward) 2016-11-23 11:44:00

1.是2.在big O notation中是一样的你想O(n)跟O(n+1)一不一样就好

楼主: gary19941208 2016-11-23 12:06:00

我也觉得是一样的，所以才觉得D选项是不是也能选

作者: hopward (hopward) 2016-11-23 12:19:00

阿不对看错题目了他是问有几条path欸

楼主: gary19941208 2016-11-23 12:26:00

哦！！我也看错了，以为他问path长度...

作者: hopward (hopward) 2016-11-23 12:26:00

看有几个leaf就有几条path，所以是2^(ha-1)+2^(hb-1)吧

作者: aa06697 (todo se andarà) 2016-11-23 17:25:00

要加big O喔未必是full

作者: hopward (hopward) 2016-11-23 23:58:00

谢提醒一开始还想说那O是干嘛的哈哈

继续阅读