[理工] [資結] 樹高

[brad84622 (brad84622)]

想知道為什麼樹高可以用 O(g(n))這種形式來表示
O(g(n))不是計算時間複雜度的嗎

定義是收集{f(n)|存在c>0 n0>0 使得 0<=f(n)<=c*g(n)}

如果是高度的話那n0又會是多少呢? n0不是表示某個時間點嗎
讀到這邊蠻困惑的@@
不是很能理解說一棵樹高是5分鐘之類的
想知道我哪裡理解有錯誤

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 119.14.94.204
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1469989532.A.21D.html
推 A4P8T6X9: big O 不是表示時間的，是函數的大小。
→ A4P8T6X9: 可以想成，如果在某一個 n 之後 g 的值都會大於 f 的，
→ A4P8T6X9: 那就是f=O(g)。
推 h42318: 我覺得你可以往search的概念下去想
好的 謝謝你 明白了
→ h42318: 從任一個bottom 的點往上找root
→ h42318: 二元樹最大高度是n, 最小高度是log(n+1)
→ h42318: 所以二元樹的time complexity 是O(n)
→ h42318: 因為最多花費n時間 最少花費log(n+1）時間
→ gigayaya: f(x)=O(g(n)) 你用中文念一遍你就懂了
※ 編輯: brad84622 (180.217.186.203), 08/01/2016 23:59:57