这个算法的大 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) 时间内运行s。一旦过去，它应该在 O(lgn) 时间内运行ning，因为它对每个元素进行排序。

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

Answer 1

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

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

Answer 2

Since this is a merge sort, I know from my research that the big-O complexity of this algorithm is O(n lgn). [...] My question is, can somebody confirm that this piece of code is running in O(n lgn) time?

不需要展示，因为归并排序已经在O(n lg(n))时间证明到运行。但是，如果您想观察它，则需要尝试使用越来越大的输入值。您可能想用您的输入值和计时结果更新您的 post。

However, when I run my timing tests, the results I get do not suggest that this is running in O(n lgn) time. [...] If not, I would like to know where I am going wrong in my understanding.

我认为您可能误解了 Big-Oh 符号实际上试图告诉您的内容。当输入变得足够大时，Big-O 会为您提供算法渐近上限的 近似值 。（"large" 是 "large enough" 的方式因算法而异，需要通过实验找到。关键是这个值 确实存在 并且我们表示它更抽象。）

换句话说，Big-O 告诉您算法最差情况下的性能可能是 N变得非常大。由于这是最坏的情况，这也意味着，它在某些情况下可能表现得更好，但我们通常不关心这些。（如果您有兴趣，请查看 Big-Omega 和 Big-Theta。）例如，如果您有一个 "small-enough" 列表，合并排序可以运行比快速排序快，这经常被使用作为优化。

它也是一个近似值，因为常量和其他多项式项 而不是 显示为符号的一部分。例如，一些时间复杂度为 500x^2 + 15x + 9000 的假设算法将被写为 O(n^2).

删除较低项的一些原因包括：

相对大小：由于n趋于正无穷大，较大的n^2项占主导地位；与 largest/dominating 项相比，较低项对总成本的贡献越来越小 ——就像在湖中加入几滴或几桶水；

方便：阅读和理解O(n^2)比没有实际好处的又长又复杂的多项式更容易

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

What is the big-O complexity of this algorithm?

java

sorting

algorithm

performance

big-o