Ex_1_5_04.md

title	date	draft	tags	categories
Algorithm4 Java Solution 1.5.04	2019-08-21 17:21:57 +0800	false	JAVA	TECH archives

1.5.04

Problem:

Estimate the minimum amount of time (in days) that would be required for quick-find to solve a dynamic connectivity problem with 10^9 sites and 10^6 input pairs, on a computer capable of executing 10^9 instructions per second. Assume that each iteration of the inner for loop requires 10 machine instructions.

Solution：

input: $10^6$ union: N, $N=10^9$

$10^6 * 10^9 * 10 / 10^9 = 115.741 $ days