Research Space for Linear Algebra & Discrete Mathematics
這題應該是Bottom-up方建立Heap所以是O(n)這題的解法是：設樹高為k,k=lg(n+1)，n為node數則cost = (i=1,k)Σ[2^(i-1)*(k-1)] = S然後將S展開為①2S為②②-①後簡化得2^(k)-k-1 = n-lg(n)-1
張貼留言
1 則留言:
這題應該是Bottom-up方建立Heap
所以是O(n)
這題的解法是：
設樹高為k,k=lg(n+1)，n為node數
則cost = (i=1,k)Σ[2^(i-1)*(k-1)] = S
然後將S展開為①
2S為②
②-①後簡化
得2^(k)-k-1 = n-lg(n)-1
張貼留言