java - 这个算法的大 O 复杂度是多少？

Question

我有一个我在下面写的函数。这个函数本质上是一个合并排序。

public static long nlgn(double[] nums)  {

        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++;
            }
        }

        return nuts;
    }

由于这是归并排序，我从研究中得知该算法的大 O 复杂度为 O(n lgn)。但是，当我运行我的计时测试时，我得到的结果并不表明这是在 O(n lgn) 时间内运行的。不过似乎是 O(n lgn) 时间，因为直到我们到达开头的两个 for 循环的末尾。它在 O(n) 时间内运行。一旦过去，它应该在 O(lgn) 时间内运行，因为它对每个元素进行排序。

我的问题是，有人可以确认这段代码在 O(n lgn) 时间内运行吗？如果不是，我想知道我的理解哪里出了问题。

Answer 1

O(nlogn) 是渐近紧界。也就是说，只有当 n 足够大时，它的运行时间才接近复杂度。当n较小时，由于函数调用开销等诸多因素，边界不紧。

你可以把 n 变大，然后比较输入之间的比率，看它是否接近 O(nlogn)。虽然我真的怀疑你必须让 n 有多大......