2.2.27 #
解答 #
大致上会是一个对数函数，用 Excel 做了简单的拟合。
原始数据：
表中的 n 代表某一个子数组用尽时两个子数组之和，rest 是另一个未用尽的子数组平均剩余长度，times 代表出现次数，表中删去了出现次数小于 100 次的数据。
| n | rest | times |
|---|---|---|
| 2 | 0.331378 | 48576 |
| 3 | 0.333894 | 213568 |
| 6 | 0.603899 | 48576 |
| 7 | 0.596223 | 82496 |
| 14 | 0.773263 | 48576 |
| 15 | 0.796285 | 16960 |
| 29 | 0.879808 | 15808 |
| 30 | 0.883432 | 16960 |
| 60 | 0.950848 | 15808 |
| 61 | 0.935764 | 576 |
| 121 | 0.985163 | 7616 |
| 122 | 0.96875 | 576 |
| 243 | 0.93608 | 3520 |
| 244 | 1.147569 | 576 |
| 487 | 0.942255 | 1472 |
| 488 | 1.020833 | 576 |
| 975 | 1.078125 | 448 |
| 976 | 1.024306 | 576 |
| 1952 | 1.129464 | 448 |
代码 #
var arraySize = 1000000;
var sort = new NotifiedMergeSort(arraySize);
for (var i = 0; i < 100; i++)
{
var data = SortCompare.GetRandomArrayInt(arraySize);
sort.Sort(data);
}
Console.WriteLine("n\trest\ttimes");
for (var i = 0; i < sort.NArraySize.Length; i++)
{
if (sort.NArraySize[i] != 0)
Console.WriteLine(i + "\t" + sort.NArraySize[i] / sort.NArraySizeTime[i] + "\t" + sort.NArraySizeTime[i]);
}
// 大致上是一个对数函数