为什么这个都能过啊???

P2249 【深基13.例1】查找

xs_siqi @ 2023-08-20 09:07:10

写了一个随机步长二分(((

测了好几发跑得都特别快,没写快输,甚至只比正常程序慢了两三倍的样子。。。

想问一下这个算法的复杂度大概是多少。。

#include<bits/stdc++.h>
#define WUDIAKIOI 666
using namespace std;
const int maxn=1e6+5;
const int DR[4]={1145,1919,233,WUDIAKIOI};
const int mod=1011451423;
int n,k,a[maxn];
int RF(int d){
    int l=1,r=n,tms=0;
    while(l<=r){
        int rid=(l+r)>>1;
        tms++;
        if(tms>2000)return l;//避免运气太差的情况
        if(a[rid]<d){
            l=l+((rand()%1000)*(rand()%1000))%(rid-l+1)+1;}//因为步长最多是500000的,所以rand出来的东西开大一点
        else{
            r=r-((rand()%1000)*(rand()%1000))%(r-rid+1)-1;}}
    return l;}
void read(int &x){
    x=0;char ch=getchar();
    while(ch<'0'||ch>'9')ch=getchar();
    while('0'<=ch&&ch<='9')x=x*10+ch-'0',ch=getchar();}
signed main(){
    srand((int)time(NULL));
    read(n),read(k);
    for(int i=1;i<=n;i++)read(a[i]);
    for(int x,i=1;i<=k;i++){
        read(x);int p=RF(x);
        if(a[p]!=x)printf("-1 ");
        else printf("%d ",p);}
    return 0;}

by xs_siqi @ 2023-08-20 09:13:39

期望应该是步长为 \frac{1}{4}


by Killer_joke @ 2023-08-20 09:37:51

@xs_siqi

单次询问还是 O(\log n) 的。

如果在区间内均匀随机。期望比较次数渐进意义上大约是 2\ln 2 (约1.386) 倍,但是因为随机数计算和访问的原因实践中会慢比较多。


by ZoeZhang @ 2023-08-20 15:33:27

@xs_siqi 什么叫随机步长二分啊,有相关资料吗,网上没搜到(还是我太菜了)


by xs_siqi @ 2023-08-20 16:25:26

@ZoeZhang 有没有一种可能,这是我随便取的名字


by xs_siqi @ 2023-08-20 16:26:54

@Killer_joke 我草真的是这样,我一开始以为这个效率很慢的


by ZoeZhang @ 2023-08-20 16:42:55


by Wangxun @ 2023-08-20 17:05:19

@xs_siqi

期望步长为 \frac{1}{4},有没有考虑先验概率?


by Wangxun @ 2023-08-20 17:05:57

@xs_siqi

在二分节点不在中间时,两边的先验概率不同。


by Wangxun @ 2023-08-20 17:25:44

@xs_siqi

把原问题抽象,先验概率均匀分布的话,假设区间长为 1,二分的值为 p,左边的先验概率为 p,右边的先验概率为 1-p

下一个期望步长 E(len) = E(p^2+(1-p)^2)

= E(2 \times p^2 - 2 \times p +1)

根据期望的线性性质:

E(2 \times p^2 - 2 \times p +1) = 2E(p^2) -2E(p)+1

E(p) = \frac{1}{2}

E(p^2) = \int_{0}^{1} x^2 dx = \frac{1}{3}

所以 E(len) = \frac{2}{3}

而所谓“期望步长”就是 1-E(len) = \frac{1}{3}


by xs_siqi @ 2023-08-20 17:33:42

@Wangxun 我草,超级大神


| 下一页