数据结构之合并 - HZH's Blog - 自闭症
数据结构之合并
nbdhhzh
posted @ 2015年6月27日 23:19
in 算法
, 595 阅读
最近学习了一些东西提高了一下姿势水平。
写篇blog。
set启发式合并
时间复杂度nlog^2(n),空间复杂度n
空间复杂度显然。
时间复杂度证明：考虑一个元素，考虑他被从一个set拿到另一个set中的次数
由于set.size()倍增，所以最多log次。
再加上set本身的log所以是log^2。
平衡树的合并也一样。
线段树合并
时间复杂度nlogn，空间复杂度nlogn。
空间复杂度显然。
时间复杂度证明：每次合并都会减少一个点，最多减少nlogn个点。
可并堆
时间复杂度nlogn，空间复杂度n
这玩意儿最近新学的。感觉蛮giang的。
看了一下blog。大概就是利用左偏的性质，导致size倍减，所以也是一个log。
但是这玩意儿之资磁找最小值。
其他我也不知道了蛤蛤蛤。。
2022年8月26日 20:15
Every year Students Struggle to acquire the Pass marks in 10th Examination. Student Download Assam HSLC Question Paper 2023 After Regular Prepare to Participate in must take a printout of Assam Board HSLC Model Paper 2023 available our Website. Student’s use Previous Paper and Start Preparation Assam HSLC Final Exam 2023 Every year Students Struggle to acquire the Pass marks in 10th Examination. SEBA Question Paper Student Download Assam HSLC Question Paper 2023 After Regular Prepare to Participate in must take a printout of Assam Board HSLC Model Paper 2023 available our Website. Student’s use Previous Paper and Start Preparation Assam HSLC Final Exam 2023