3.1.36 #
解答 #
实验结果如下，增长级为 O(N) ，但速度很快。
其实只要列出《双城记》不同长度的单词数目，原因就一目了然了。
大部分单词都集中在中间长度，因此大部分访问也集中在数组中部。
二分查找在访问数组中部的元素时速度很快，因此结果好于预期。
代码 #
var n = 8000;
var multiplyBy2 = 5;
var repeatTimes = 5;
double lastTime = -1;
Console.WriteLine("n\ttime\tratio");
for (var i = 0; i < multiplyBy2; i++)
{
Console.Write(n + "\t");
long timeSum = 0;
for (var j = 0; j < repeatTimes; j++)
{
var st = new BinarySearchSt<string, int>();
var sw = Stopwatch.StartNew();
FrequencyCounter.MostFrequentlyWord("tale.txt", n, 0, st);
sw.Stop();
timeSum += sw.ElapsedMilliseconds;
}
timeSum /= repeatTimes;
Console.Write(timeSum + "\t");
if (lastTime < 0)
Console.WriteLine("--");
else
Console.WriteLine(timeSum / lastTime);
lastTime = timeSum;
n *= 2;
}