这些结果如何证明我的方法在 O(n lgn) 时间内是 运行？

Question

我有一个我写在下面的方法。

public static long nlgn(double[] nums)  {

        long start = System.nanoTime();

        if(nums.length > 1)     {
            int elementsInA1 = nums.length/2;
            int elementsInA2 = nums.length - elementsInA1;
            double[] arr1 = new double[elementsInA1];
            double[] arr2 = new double[elementsInA2];

            for(int i = 0; i < elementsInA1; i++)
            arr1[i] = nums[i];

            for(int i = elementsInA1; i < elementsInA1 + elementsInA2; i++)
            arr2[i - elementsInA1] = nums[i];

            nlgn(arr1);
            nlgn(arr2);

            int i = 0, j = 0, k = 0;

            while(arr1.length != j && arr2.length != k) {
                if(arr1[j] <= arr2[k]) {
                    nums[i] = arr1[j];
                    i++;
                    j++;
                } else {
                    nums[i] = arr2[k];
                    i++;
                    k++;
                }
            }

            while(arr1.length != j) {
                nums[i] = arr1[j];
                i++;
                j++;
            }
            while(arr2.length != k) {
                nums[i] = arr2[k];
                i++;
                k++;
            }
        }

        double max = nums[nums.length - 1];
        double min = nums[0];

        double[] farthestPair = {max, min};

        long end = System.nanoTime();

        return (end - start);
    }

这基本上是一个合并排序操作，一旦排序，就会找到最小和最大的数字。我相信这种方法可以在 O(n lgn) 时间内运行。但是，当我 运行 函数的输入大小在每个 运行（1000、2000、4000 等）时加倍，当我以纳秒为单位计时时，我得到以下结果。

First pass: (0.12) seconds
Second pass: (0.98) seconds
Third pass: (0.91) seconds
Fourth pass: (0.90) seconds
Fifth pass: (1.33) seconds

我的问题是，鉴于这些结果，这些结果是否表明此方法在 O(n lgn) 时间内 运行 有效？

Answer 1

如果你有算法的源代码，你应该分析它而不是做运行时基准测试。

如果是递归函数，请查看 master theorem.

在你的函数中你做了 2 次大小为 n / 2 的递归调用，所以 a = 2, b = 2 和 f(n) = 2n，因为在你的前两个 for 循环中你遍历了所有数组 (n)并使用最后三个 while 循环再次迭代所有数组大小 (n)，因此 2n.

如果你应用主定理，它会给出结果 Θ(n ln(n))，所以 O(n ln(n)) 也是正确的。