Trung bình, bạn cần bao nhiêu lần nhấp để xem tất cả các câu hỏi trong cơ sở dữ liệu?Cách tiếp cận câu hỏi thuật toán này?
Cách tiếp cận bắt buộc cho các câu hỏi như vậy là gì?
Tại sao chúng ta không chạy mô phỏng và phát hiện ra?
<?php
function simulate($size) {
$range = range(1, $size);
$hits = 0;
$hit = array();
while(count($hit) != $size) {
$rand = array_rand($range);
$hit[$rand] = 1;
$hits++;
}
return $hits;
}
for ($j=10; $j<101; $j+=10) {
$res = array();
for ($i=0; $i<10; $i++) {
$res[] = simulate($j);
}
echo "for size=$j, avg=" . array_sum($res)/10 . "<br />";
}
Output:
for size=10, avg=35.9
for size=20, avg=68.8
for size=30, avg=123.3
for size=40, avg=176.9
for size=50, avg=205.9
for size=60, avg=276.8
for size=70, avg=304.9
for size=80, avg=401.9
for size=90, avg=371
for size=100, avg=617.7
Đây là một câu hỏi toán học chứ không phải là một thuật toán. Là sdcvvc said, đây là vấn đề của người thu phiếu giảm giá nổi tiếng.
Giả sử bạn có n câu hỏi để "thu thập". Cho X là random variable biểu thị số lượng nhấp chuột được yêu cầu. Nếu chúng ta định nghĩa Xi là số lần nhấp chuột từ thời điểm hiện tại chúng tôi có thắc mắc (i-1) đến thời điểm chúng tôi có i câu hỏi, sau đó:
X = X1 + X2 + ... + Xn
do linearity of the expected value:
E (X) = E (X1 + X2 + ... + Xn) = EX1 + EX2 + ... + EXn
Nếu chúng ta kiểm tra Xi, chúng ta thấy rằng trong thực tế nó có geometric distribution với p = (n-i + 1)/n, do đó giá trị trung bình của n/(n-i + 1). Do đó:
EX = n * (1/n + 1/(n-1) + ... + 1/2 + 1/1) = n * Hn
đâu Hn là thứ n Harmonic number, mà có thể được xấp xỉ bằng ln n:
EX ~ = n * ln n
Bạn có thể chạy một mô phỏng đơn giản và kiểm tra xấp xỉ này.
Chúng tôi có xác suất 1/n'của mỗi câu hỏi với mỗi nhấp chuột không? –
@Zenzen: vâng, chúng tôi có. – Lazer
Bạn đã tìm được cách tiếp cận chính xác cho câu hỏi như vậy: đăng nó lên stackoverflow. ;) – x4u