[理工] 資結 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是幹嘛的哈哈

繼續閱讀