关于最值分治的复杂度问题
  • 板块学术版
  • 楼主spdarkle
  • 当前回复3
  • 已保存回复3
  • 发布时间2023/11/28 00:57
  • 上次更新2023/11/28 13:57:45
查看原帖
关于最值分治的复杂度问题
507718
spdarkle楼主2023/11/28 00:57

众所周知,假设我们每次需要以 O(len)O(len) 处理一层,那么最值分治的复杂度最优 O(nlog⁡n)O(n\log n) 最劣 O(n2)O(n^2),那在随机数据下的期望复杂度是?

虽然少部分情况可以通过启发式合并规避掉划分不均的问题

2023/11/28 00:57
加载中...