2.2.27

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

解答

大致上会是一个对数函数,用 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

代码

using System;
using Merge;

namespace _2._2._27
{
    /*
     * 2.2.27
     * 
     * 子数组长度。
     * 用归并将大型随机数组排序,
     * 根据经验用 N (某次归并时两个子数组的长度之和)
     * 的函数估计当一个子数组用尽时另一个子数组的平均长度。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            int arraySize = 1000000;
            NotifiedMergeSort sort = new NotifiedMergeSort(arraySize);
            for (int i = 0; i < 100; i++)
            {
                int[] data = SortCompare.GetRandomArrayInt(arraySize);
                sort.Sort(data);
            }

            Console.WriteLine("n\trest\ttimes");
            for (int 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]);
            }
            // 大致上是一个对数函数
        }
    }
}

另请参阅

Merge 库

上一题 下一题