风人 @ 2020-05-13 21:49:45
前置：我不是向北方等，我只是觉得有点问题，欢迎指出问题并踩爆我
题解原文
可以看到作者的复杂度说是O(n)，然而他是通过类似二分，那就是log n次，每次扫描上次的半长区间，并且读入不也是O(n)的，为何总复杂度为O(n)
谢
by FZzzz @ 2020-05-13 21:54:01
快速选择的复杂度不是假的吗？
by FZzzz @ 2020-05-13 21:54:12
但是确实是期望
by iMya_nlgau @ 2020-05-13 21:54:20
@风人 因为它每次划分只递归了含第
by FZzzz @ 2020-05-13 21:55:27
by Kniqht @ 2020-05-13 21:57:22
@FZzzz
by FZzzz @ 2020-05-13 21:58:31
@Ax_Plus 自己设的一个函数，表示复杂度
by xhQYm @ 2020-05-13 21:59:17
@FZzzz 莫名感觉向北方
by FZzzz @ 2020-05-13 22:00:47
@qym2008 ？bfw 是
by xhQYm @ 2020-05-13 22:01:26
@FZzzz 就是说设的复杂度名字很像
by hly1204 @ 2020-05-13 22:01:35
@风人 假设期望可以分成2等分的话，就是一个等比数列求和公式，因为每次只往其中一半递归。