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