关于时间复杂度的分析

提交记录

点分治按照重心递归的时间复杂度应为 O(n \log n)的。然后分析时间复杂度的重点应在于我代码中的 Calc 时间复杂度。问问佬们分析的对不对。

以下为我自己分析的过程。

考虑最坏情况。
每次分别会找 1,2,4,8, ... 个 重心，那么可以通过等差数列求和公式算出调用 Calc 函数的次数级别应该为 O(n)。

再看它本身的复杂度。

因为我们本质是在分治，所以在同阶的情况下（比如此时需要遍历树的大小为 n/2，遍历两次），所以每同阶次 Calc 中遍历树的部分应该总体为 O(n) 的，显然有 \log n 个同阶次。
然后我的代码 dfs 函数中遍历到每个点都会遍历一遍询问，也就是复杂度还要乘 m。

所以代码总体时间复杂度为 O(n \times m \times \log n)。可以通过此题。

各位佬们，我扯得合理嘛/kel