关于第一篇题解的复杂度分析

P1923 【深基9.例4】求第 k 小的数

风人 @ 2020-05-13 21:49:45

前置：我不是向北方等，我只是觉得有点问题，欢迎指出问题并踩爆我

题解原文

可以看到作者的复杂度说是O(n)，然而他是通过类似二分，那就是log n次，每次扫描上次的半长区间，并且读入不也是O(n)的，为何总复杂度为O(n)

谢

by 囧仙 @ 2020-05-13 22:01:59

@风人这题其实最好\verb!random_shuffle!一下，不然的确可能被卡（参考快排卡法）

但是复杂度的确是\mathcal O(n)。

每一次操作的区间折半，也就是n+\frac{n}{2}+\frac{n}{4}+\cdots\approx 2\times n。

by FZzzz @ 2020-05-13 22:02:16

@qym2008 ……不都是这么设的吗，是你自己被 bfw 带歪了吧……

by 风人 @ 2020-05-13 22:02:26

@FZzzz @qym2008 @Ax_Plus @Sapphire6575737973

谢谢您们，我尝试理解下

by 风人 @ 2020-05-13 22:02:53

@hly1204 哦嗯嗯，谢谢

by 风人 @ 2020-05-13 22:04:28

@囧仙谢谢您了~~一道题又见面了~~ 谢谢呢

by NaCly_Fish @ 2020-05-13 22:17:51

@囧仙不 random_shuffle 的话，会被卡成 \text O(n^2) 吧

by 风人 @ 2020-05-13 22:22:13

捕捉神鱼

上一页 |