1.5.22 #
解答 #
平方级别算法在输入加倍后耗时应该增加四倍，线性则是两倍。
下面给出我电脑上的结果，数据量较大时比较明显：
N:16000
quick-find
平均次数：8452
用时：143 比值：4.46875
quick-union
平均次数：7325
用时：202 比值：3.25806451612903
weighted-quick-union
平均次数：6889
用时：1
N:32000
quick-find
平均次数：15747
用时：510 比值：3.56643356643357
quick-union
平均次数：15108
用时：801 比值：3.96534653465347
weighted-quick-union
平均次数：17575
用时：3 比值：3
N:64000
quick-find
平均次数：33116
用时：2069 比值：4.05686274509804
quick-union
平均次数：38608
用时：4635 比值：5.78651685393258
weighted-quick-union
平均次数：34850
用时：6 比值：2
代码 #
long lastTimeQuickFind = 0;
long lastTimeQuickUnion = 0;
long lastTimeWeightedQuickUnion = 0;
for (var n = 2000; n < 100000; n *= 2)
{
Console.WriteLine("N:" + n);
var quickFindUf = new QuickFindUf(n);
var quickUnionUf = new QuickUnionUf(n);
var weightedQuickUnionUf = new WeightedQuickUnionUf(n);
// quick-find
Console.WriteLine("quick-find");
var nowTime = RunTest(quickFindUf);
if (lastTimeQuickFind == 0)
{
Console.WriteLine("用时：" + nowTime);
lastTimeQuickFind = nowTime;
}
else
{
Console.WriteLine("用时：" + nowTime + " 比值：" + (double)nowTime / lastTimeQuickFind);
lastTimeQuickFind = nowTime;
}
Console.WriteLine();
// quick-union
Console.WriteLine("quick-union");
nowTime = RunTest(quickUnionUf);
if (lastTimeQuickUnion == 0)
{
Console.WriteLine("用时：" + nowTime);
lastTimeQuickUnion = nowTime;
}
else
{
Console.WriteLine("用时：" + nowTime + " 比值：" + (double)nowTime / lastTimeQuickUnion);
lastTimeQuickUnion = nowTime;
}
Console.WriteLine();
// weighted-quick-union
Console.WriteLine("weighted-quick-union");
nowTime = RunTest(weightedQuickUnionUf);
if (lastTimeWeightedQuickUnion == 0)
{
Console.WriteLine("用时：" + nowTime);
lastTimeWeightedQuickUnion = nowTime;
}
else
{
Console.WriteLine("用时：" + nowTime + " 比值：" + (double)nowTime / lastTimeWeightedQuickUnion);
lastTimeWeightedQuickUnion = nowTime;
}
Console.WriteLine();
Console.WriteLine();
}
// 进行若干次随机试验，输出平均 union 次数，返回平均耗时。
static long RunTest(Uf uf)
{
var timer = new Stopwatch();
var total = 0;
var repeatTime = 10;
timer.Start();
for (var i = 0; i < repeatTime; i++)
{
total += ErdosRenyi.Count(uf);
}
timer.Stop();
Console.WriteLine("平均次数：" + total / repeatTime);
return timer.ElapsedMilliseconds / repeatTime;
}