1.5.5

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

$10^6$ 条连接 = $10^6$ 组输入。
对于 quick-find 算法,每次 union() 都要遍历整个数组。
因此总共进行了 $10^9 \times 10^6 = 10^{15}$ 次 for 循环迭代。
每次 for 循环迭代都需要 $10$ 条机器指令,
因此总共执行了 $10 \times10^{15} = 10^{16}$ 条机器指令。
已知计算机每秒能够执行 $10^9$ 条机器指令,
因此执行完所有指令需要 $10^{16} / 10^9 = 10^7$ 秒 = $115.74$ 天。

上一题 下一题