求解析:这随机化是怎么降下来复杂度的?
  • 板块学术版
  • 楼主OrinLoong
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/9/30 12:56
  • 上次更新2024/9/30 17:13:00
查看原帖
求解析:这随机化是怎么降下来复杂度的?
539345
OrinLoong楼主2024/9/30 12:56

没太搞懂[P8817,假期计划]的这份随机化题解
O(N2)O(N^2)的暴力处理点间距离之后,如果不用随机化直接搜,应该是一棵O(N4)O(N^4)级别的搜索树;如果用了随机化,分成4个点集,应该就是一棵O((N4)4)=O(N444)O((\frac{N}{4})^4)=O(\frac{N^4}{4^4})的搜索树,但是它的正确率又只有144\frac{1}{4^4},所以期望下来应该要随机444^4次才能对;那这复杂度不就乘回去了吗?求解答!玄关。

2024/9/30 12:56
加载中...