这个算法的大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)时间内运行。尽管在两个for循环的末尾之前，它的运行时间是O(n)。但一旦超过此点，每个元素的排序应该在O(lgn)时间内完成。

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

- Omar N

---

非常类似于http://stackoverflow.com/questions/33716270/how-do-these-results-prove-my-method-is-running-in-on-lgn-time的问题。 - orlp

如果您发现问题已解决，请不要忘记接受！ - Euclid Ye

你得到了什么结果，它们除了O(n lgn)之外还有什么其他建议吗？（忽略任何小于一秒的结果，增加问题规模。）如果O(lgn)时间不是打字错误，请你为这个结果辩护一下好吗？ - greybeard

提示：坚果从哪里来？如果您使用if（nums.length <= 1）return nums;，则缩进级别将减少一个。 for（int i = elementsInA1; i <elementsInA1 + elementsInA2; i ++）arr2 [i - elementsInA1] = nums [i];看起来比for（int i = 0; i <elementsInA2; i ++）arr2 [i] = nums [elementsInA1 + i];更复杂。）（已删除有关_space_复杂性的错误评论-我的错）。 - greybeard

Answer 1

O(nlogn)是一个渐进紧密的时间复杂度。这意味着只有当n足够大时，它的运行时间才接近该复杂度。当n很小时，由于函数调用开销和许多其他因素，此界限并不紧密。

您可以增加n，比较输入之间的比率，看是否接近O(nlogn)。虽然我真的怀疑您必须将n设置多大才能做到...

- Euclid Ye

---

谢谢您提供这些信息，这很有帮助。您能解释一下您真正怀疑n需要多大的含义吗？ - Omar N

因为根据渐近符号的定义，比如说 T(n) = theta(nlogn)。这意味着对于任何大于某个常数n0的n，存在常数c1和c2，使得c1 nlogn <= T(n) <= c2nlogn。请注意，这里的n0是数学中的抽象概念，因为我们只是说存在一个n0，但我们不知道它应该有多大才能使近似值真正接近你想要的值。 - Euclid Ye

Answer 2

由于这是一种归并排序，从我的研究中得知该算法的大O复杂度为O(n lgn)。我的问题是，有人能确认这段代码是否在O(n lgn)时间内运行吗？不需要展示它，因为归并排序已经被证明可以在O(n lg(n))时间内运行。但是如果您想观察它，您需要尝试使用越来越大的输入值进行实验。您可能需要更新您的帖子，包括您的输入值和计时结果。然而，当我运行计时测试时，所得到的结果并没有表明这是以O(n lgn)时间运行的。如果不是，请告诉我我理解错了哪里。

我认为您可能误解了大O符号实际想要告诉您的内容。大O给出了算法渐近上限的近似值，当输入足够大时。(“足够大”对于不同的算法会有所不同，需要通过实验来确定。重点在于这个值确实存在，我们更抽象地表示它。)

换句话说，大O告诉您算法在N变得非常大时可能的最坏情况性能。由于这是最坏情况下的表现，也意味着在某些情况下它可能会表现得更好，但我们通常不关心这些。(如果您感兴趣，请了解大Omega和大Theta。)例如，如果您有一个“足够小”的列表，归并排序可以比快速排序运行得更快，这通常被用作优化。

这也是一种近似，因为常数和其他多项式项没有作为符号的一部分显示。例如，某些假设的算法时间复杂度为500x^2 + 15x + 9000将被写成O(n^2)。

放弃低阶项的一些原因包括：

- 相对大小：随着n趋向正无穷大，更大的n^2项会占据主导地位；与最大/支配项相比，较低的项对总体成本的贡献越来越小——就像往湖里加几滴或几桶水一样； - 方便：阅读和理解O(n^2)比阅读长而更复杂的多项式方便，并且没有实际好处。

- code_dredd