In computer science, the randomized quicksort algorithm has expected runtime O(nlogn). How does linearity of expectation allow us to show this?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3773 |
3 | Radewoosh | 3646 |
4 | ecnerwala | 3624 |
5 | jqdai0815 | 3620 |
5 | Benq | 3620 |
7 | orzdevinwang | 3612 |
8 | Geothermal | 3569 |
8 | cnnfls_csy | 3569 |
10 | gyh20 | 3447 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | awoo | 161 |
2 | maomao90 | 160 |
3 | nor | 157 |
4 | atcoder_official | 156 |
4 | cry | 156 |
6 | -is-this-fft- | 155 |
7 | maroonrk | 154 |
8 | adamant | 153 |
9 | Um_nik | 151 |
10 | djm03178 | 146 |
In computer science, the randomized quicksort algorithm has expected runtime O(nlogn). How does linearity of expectation allow us to show this?
Let, x1 < = x2 < = x3....... < = xn
and
p1 + p2 + p3 + ....... + pn = 1
We all know that average of x1, x2, x3......., xn is in [x1,xn] and it is easy to understand.
In a contest, I assumed Expected value = p1 * x1 + p2 * x2 + p3 * x3 + ....... + pn * xn is in [x1,xn] regardless how probability is distributed that means the sum of probability can be 1 in many different ways.
My assumption was right and got ac. I'm interested to know the proof.
TIA
Question 01:
Is there any technique where generating random number within a range is equiprobable ?
Question 02:
What is the extra advantage of the following method 02,03,04 ?
srand(time(NULL);
//Method 01: general approach
int myrand(int mod){
return rand()%mod;
}
//Method 02: Taken form red coder submission.
int myrand(int mod) {
int t = rand() % mod;
t = (1LL*t*RAND_MAX + rand()) % mod;
return t;
}
//Method 03: Taken from red coder submission.
int myrand(int mod) {
return (int) ( (((double) rand() / RAND_MAX) * (mod) ));
}
//Method 04 : Taken from red coder submission.
inline int myrand(int mod) {
return (((long long )rand() << 15) + rand()) % mod;
}
Updated : Idea from diko.
auto seed = chrono::high_resolution_clock::now().time_since_epoch().count();
std::mt19937 mt(seed);
int myrand(int mod) {
return mt()%mod;
}
The problem was set in acm icpc preliminary contest 2017 in Dhaka site. Problem Link : E.Anti Hash
Problem is : you will given a string S of length N consisting of lowercase letters (a-z) only.Also given a base B and mod-value M for doing polynomial hashing. Note : B and M are both prime.
Your task is to find another string T, satisfying all of the following constraints: Length of T is exactly N. T consists of only lowercase letters (a-z). T and S have the same hash value that means, collision happens. For hashing in both case you have to use B and M.
Any idea? Thanks in advance.
If a String is : "Topcoder" and all of it's suffix are :
r,er,der,oder........pcoder,Topcoder
Now consider c++ code:
std::string str = "Topcoder";
const char* pointer = &str[1];
cout<<pointer<<'\n';
Output is: opcoder
What is the complexity of generating of above suffix upto 1 index of length 7? Linear or Constant ?
Is 10^9 computation is possible before 2.00 seconds? If not possible,how my solution works of following problem? Problem link: http://mirror.codeforces.com/problemset/problem/851/C Submission: http://mirror.codeforces.com/contest/851/submission/30089349
Название |
---|