1. PTT
  2. Grad-ProbAsk

[理工] 資結 union-by-height和simple-find

作者: q5332159 (chiu)   2017-11-12 01:23:00
https://i.imgur.com/d0HmD0g.jpg
想問為什麼樹高頂多是O(log n)?
謝謝大家~~><
作者: sarsman (DeNT15T♠)   2017-11-12 01:55:00
思考如何輸入能使樹高增加，再想對應的點數應該很明顯
作者: q5332159 (chiu)   2017-11-12 14:17:00
不好意思還是不太懂><可以說明一下嗎？謝謝!!
作者: htc018220 (ZhangHan)   2017-11-12 21:57:00
最好的狀況是：一個當root，其他當子點，level=2最壞的情況是：兩兩Union，每次Union樹高加一，8個數Union，level=4，16 個數Union，level=5.....近似log n
作者: q5332159 (chiu)   2017-11-13 00:58:00
喔喔喔懂了~~謝謝><><!!
繼續閱讀
[理工] 線代 反矩陣小問題SIGNAL2017[線代] 105台大 求inverseking8313[理工] 離散 邏輯springleaf1[理工] 工數 積分問題pttrzong[理工] C++指標與陣列問題wayneshiau[計組]101台聯大 pipelineking8313[理工] OS time-sharing 恐龍原文描述的問題TMDTMD2487[理工] 離散 環狀排列WachinMs[理工] 計組 張凡上冊p.28defsrisars[理工] 幾個觀念問題 OS/計組leoone

Links booklink

Contact Us: admin [ a t ] ucptt.com