#include<iostream>
#include<algorithm>
#include<ctime>
#include<cstdlib>
#include<set>
#include<random>
#pragma GCC optimize("Ofast")
using namespace std
;
int rand_int(int a
, int b
);
void non_repeat(int n
, int* a
) {
set
<int> s
;
default_random_engine
e(time(0));
while (s
.size() != n
) {
int m
= e();
if (s
.empty())
s
.insert(m
);
else if (s
.find(m
) == s
.end())
s
.insert(m
);
}
int i
= 0;
for (set
<int>::iterator it
= s
.begin(); it
!= s
.end(); it
++)
{
a
[i
++] = *it
;
}
}
void shuffle(int n
, int* a
) {
for (int i
= 0; i
< n
; i
++)
a
[i
] = i
;
for (int i
= 0; i
< n
- 1; i
++) {
int j
= rand_int(i
+ 1, n
- 1);
int tmp
= a
[j
];
a
[j
] = a
[i
];
a
[i
] = tmp
;
}
}
int rand_int(int a
, int b
) {
default_random_engine
e(time(0));
uniform_int_distribution
<unsigned> u(a
, b
);
return u(e
);
}
int search_x(int x
, int i
, int* ptr
, int* val
) {
while (x
> val
[i
]) {
i
= ptr
[i
];
}
return i
;
}
int A(int x
, int head
, int* ptr
, int* val
) {
return search_x(x
, head
, ptr
, val
);
}
int D(int x
, int head
, int n
, int* ptr
, int* val
) {
int m
= rand_int(0, n
- 1);
if (val
[m
] > x
)
return search_x(x
, head
, ptr
, val
);
else if (val
[m
] < x
)
return search_x(x
, ptr
[m
], ptr
, val
);
else
return m
;
}
int B(int x
, int head
, int n
, int* ptr
, int* val
) {
int max_val
= val
[head
];
int i
= head
;
int y
= -1;
for (int j
= 0; j
< sqrt(n
); ++j
) {
y
= val
[j
];
if (max_val
< y
&& y
<= x
) {
i
= j
;
max_val
= y
;
}
}
return search_x(x
, i
, ptr
, val
);
}
int C(int x
, int head
, int n
, int* ptr
, int* val
) {
int L
= sqrt(n
);
int* idx
= new int[L
];
default_random_engine
e(time(0));
uniform_int_distribution
<unsigned> u(0, n
-1);
for (int i
= 0; i
< L
; i
++)
idx
[i
] = u(e
);
int i
= head
;
int y
= -1;
int max_val
= val
[i
];
for (int j
= 0; j
< L
; ++j
) {
y
= val
[idx
[j
]];
if (max_val
< y
&& y
<= x
) {
i
= idx
[j
];
max_val
= y
;
}
}
delete []idx
;
return search_x(x
, i
, ptr
, val
);
}
int main() {
int* val
, * ptr
, * a
, n
;
cout
<< "输入n:";
cin
>> n
;
ptr
= new int[n
];
val
= new int[n
];
a
= new int[n
];
shuffle(n
, ptr
);
non_repeat(n
, a
);
sort(a
, a
+ n
);
int head
= ptr
[0];
int k
= head
;
for (int i
= 0; i
< n
; i
++) {
val
[k
] = a
[i
];
k
= ptr
[k
];
}
int i
= head
;
int m
= 0;
while (1) {
m
++;
i
= ptr
[i
];
if (m
== n
- 1) {
ptr
[i
] = -1;
break;
}
}
cout
<< "************************" << endl
;
while (1) {
cout
<< "输入i:";
cin
>> i
;
clock_t start
= clock();
int k
= 0;
int aa
;
while(k
++<100)
aa
= A(val
[i
], head
, ptr
, val
);
clock_t endA
= clock();
k
= 0;
int bb
;
while(k
++<100)
bb
= B(val
[i
], head
, n
, ptr
, val
);
clock_t endB
= clock();
k
= 0;
int cc
;
while (k
++ < 100)
cc
= C(val
[i
], head
, n
, ptr
, val
);
clock_t endC
= clock();
k
= 0;
int dd
;
while (k
++ < 100)
dd
= D(val
[i
], head
, n
, ptr
, val
);
clock_t endD
= clock();
double timeA
= (double)(endA
- start
) / CLOCKS_PER_SEC
;
double timeB
= (double)(endB
- endA
) / CLOCKS_PER_SEC
;
double timeC
= (double)(endC
- endB
) / CLOCKS_PER_SEC
;
double timeD
= (double)(endD
- endC
) / CLOCKS_PER_SEC
;
cout
<< "A:" << aa
<< " average time used is " << timeA
/100 << endl
;
cout
<< "B:" << bb
<< " average time used is " << timeB
/100 << endl
;
cout
<< "C:" << cc
<< " average time used is " << timeC
/100 << endl
;
cout
<< "D:" << dd
<< " average time used is " << timeD
/100 << endl
;
}
delete []a
;
delete []ptr
;
delete []val
;
return 0;
}
A,B,C,D分别是最普通的算法(O(n))、时间复杂度为
n
\sqrt n
n
的确定性算法，B的舍伍德算法形式以及普通的随机算法。 下图是一次运行结果： 可以看到，A,D的运行时间在同一个量级，时间复杂度为O(n)，B,C的运行时间远远小于A,D，因为B,C的时间复杂度为
O
(
n
)
。
O(\sqrt n)。
O(n
)。
