关于此题空间复杂度
查看原帖
关于此题空间复杂度
248359
Cloote楼主2024/5/24 16:11

针对做法:对于每个点开两颗线段树

个人感觉空间的分析如下:对于每个点有期望 log⁡n\log n 的不同的距离,而每个不同的距离可能会在线段树上多开 log⁡n\log n 个点,那么最后空间复杂度应该是 O(nlog⁡nlog⁡n)O(n \log n\log n) 的。也就是理论空间要开 172=28917^2=289 倍。

但是为什么实际上需要开的空间远远小于上面分析的,还是说上面的分析并不严谨。如果是在考试中,如何分析此类问题的空间复杂度?

2024/5/24 16:11
加载中...