Trong tin học, độ hiệu quả của một thuật toán tỉ lệ với tốc độ thực thi chương trình và được tính bởi \(E\left( n \right) = \frac{n}{{P\left( n \right)}}\), trong đó \(n\) là số lượng dữ liệu đầu vào và \(P\left( n \right)\) là độ phức tạp của thuật toán. Biết rằng một thuật toán có \(P\left( n \right) = {\log _2}n\) và khi \(n = 300\) thì để chạy nó, máy tính mất \(0,02\) giây. Hỏi khi \(n = 90000\) thì phải mất bao lâu để chạy chương trình tương ứng?

Số phần tử của tập hợp \(S\) là \(A_8^4 - A_7^3 = 1470\) (phần tử).

Số có 4 chữ số có dạng \(\overline {abcd} \).

Gọi \(A\) là biến cố "Số chọn được có dạng \(\overline {abc0} \) có tổng các chũ số chia hết cho 3 ", \(B\) là biến cố "Số chọn được có dạng \(\overline {abc5} \) có tổng các chữ số chia hết cho 3".

Khi đó biến cố "Số chọn được chia hết cho 15" là \(A \cup B\).

Nếu \(d = 0\), bộ 3 số \((a;b;c)\) có tổng \(a + b + c\) chia hết cho 3. Ta có các bộ số thoả mãn là: \((1;2;3),(1;2;6),(1;3;5),(1;4;7),(1;5;6),(2;3;4),(2;3;7),(2;4;6),(2;6;7)\), \((3;4;5),(3;5;7),(4;5;6),(5;6;7)\).

Từ các bộ số này có thể lập được \(13.3! = 78\) (số). Suy ra \(P(A) = \frac{{78}}{{1470}} = \frac{{13}}{{245}}\).

Nếu \(d = 5\), bộ 3 số \((a;b;c)\) có tổng \(a + b + c + 5\) chia hết cho 3, ta có các bộ thoả mãn là: \((0;1;3),(0;1;6),(0;2;5),(0;3;4),(0;3;7),(0;4;6),(1;2;7),(1;3;6),(1;4;5)\), \((2;3;5),(0;6;7),(1;5;7),(2;4;7),(2;5;6),(3;4;6),(3;6;7),(4;5;7)\).

Từ các bộ số này có thể lập được \(7.4 + 10.3! = 88\) (số). Suy ra \(P(B) = \frac{{88}}{{1470}} = \frac{{44}}{{735}}\).

Ta có: \(P(A \cup B) = P(A) + P(B) = \frac{{13}}{{245}} + \frac{{44}}{{735}} = \frac{{83}}{{735}}\).

Vậy xác suất để chọn được số chia hết cho 15 tử tập hợp \(S\) là \(\frac{{83}}{{735}}\).