如何将这些结果证明我的方法是为O（n LGN）同时运行？ [英] How do these results prove my method is running in O(n lgn) time?

问题描述

我有我写了下面的方法。

I have a method that I wrote below.

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等）的输入的大小，我得到下面的结果，当我计时它在纳米时间。

This is basically a merge sort operation that, once sorted, will find the smallest and largest numbers. I believe this method is operating in O(n lgn) time. However, when I run the function with an input size that doubles upon each run (1000, 2000, 4000, etc.), I get the following results when I time it in nano time.

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）的时间？

My question is, given these results, do these results suggest that this method is running in O(n lgn) time?

推荐答案

如果你有算法的源$ C ​​$ C，你应该分析，而不是做运行时的基准了。

If you have the source code of the algorithm, you should analyze it instead of doing runtime benchmarks.

在递归函数的情况下，看看到的主定理

In the case of recursive functions, take a look to the master theorem.

在你的功能，你做2尺寸递归调用 N / 2 ，所以 A = 2，B = 2 和 F（N）= 2 ，因为在你的两个第一对你沿着所有的阵列（n）的循环圈，并用三颗最后while循环再次全部循环数组大小（N），所以 2N 。

In your function you do 2 recursive calls with size n / 2, so a = 2, b = 2 and f(n) = 2n, because in your two first for loops you iterate along all the array (n) and with the three final while loops you iterate again all the array size (n), so 2n.

如果你申请的主定理它给你的结果Θ（N LN（N）），所以为O（n LN（N） ）是正确的了。

If you apply the master theorem it gives you as result Θ(n ln(n)), so O(n ln(n)) is correct too.

这篇关于如何将这些结果证明我的方法是为O（n LGN）同时运行？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！