algorithm - 这些结果如何证明我的方法在 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))也是正确的。