众所周知,假设我们每次需要以 O(len)O(len)O(len) 处理一层,那么最值分治的复杂度最优 O(nlogn)O(n\log n)O(nlogn) 最劣 O(n2)O(n^2)O(n2),那在随机数据下的期望复杂度是?
虽然少部分情况可以通过启发式合并规避掉划分不均的问题