有没有大佬告诉我为什么这个算法能On啊

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

Euler_Pursuer @ 2020-11-06 07:57:31

RT。I need a prove... THX

by 1saunoya @ 2020-11-06 07:58:44

期望 O(n)

by __OwO__ @ 2020-11-06 08:04:19

这个算法是今年CSP-S的初赛考点qwq

by __OwO__ @ 2020-11-06 08:09:24

T(n)=n+T(\frac{n}{2})

所以为O(n)

因为T(n)=n+\frac{n}{2}+\frac{n}{4}+\frac{n}{8}+...=2*n 忽略所有常数,所以复杂度为O(n)

@Euler_Pursuer

by wwlw @ 2020-11-06 08:14:20

蓝书上有吧

by __OwO__ @ 2020-11-06 08:17:22

但如果是快排两边都要递归下去就是O(nlogn)的了

因为

T(n)=n+2*T(\frac{n}{2})

T(n)=n+2*\frac{n}{2}+4*T(\frac{n}{4})=n+n+...+n

此处递归log2层,所以复杂度是O(nlogn)的

不需要我证明1+\frac{1}{2}+\frac{1}{4}+...\frac{1}{2^n}=2吧

by Euler_Pursuer @ 2020-11-06 08:51:02

@OwO zui huai qing kuang ne？

by __OwO__ @ 2020-11-06 08:57:08

@Euler_Pursuer 对不起我回复错了

原来是问最坏情况

今年初赛告诉我们最坏是O(n^2)的,当输入的都是同一个数的时候

by __OwO__ @ 2020-11-06 08:57:37

初赛

by __OwO__ @ 2020-11-06 08:58:13

17题的第六个

by __OwO__ @ 2020-11-06 08:58:48

我好菜qwq