java - 违反 Big-O 表示法中给定的平均时间复杂度

Question

我正在尝试实现一个解决方案，以在给定的整数列表中找到第 k 个最大的元素，其中重复项具有 O(N*log(N)) Big-O 表示法的平均时间复杂度，其中 N 是列表中元素的数量。

根据我的理解，合并排序的平均时间复杂度为 O(N*log(N)) 但是在我下面的代码中，我实际上使用了一个额外的 for 循环以及合并排序算法来删除重复项，这肯定违反了我使用 O(N*log(N)) 查找第 k 个最大元素的规则。我如何通过以大 O 表示法实现我的任务 O(N*log(N)) 平均时间复杂度来实现它？

public class FindLargest {
    public static void nthLargeNumber(int[] arr, String nthElement) {
        mergeSort_srt(arr, 0, arr.length - 1);
        // remove duplicate elements logic
        int b = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[b] != arr[i]) {
                b++;
                arr[b] = arr[i];
            }
        }

        int bbb = Integer.parseInt(nthElement) - 1;
        // printing second highest number among given list
        System.out.println("Second highest number is::" + arr[b - bbb]);
    }

    public static void mergeSort_srt(int array[], int lo, int n) {
        int low = lo;
        int high = n;
        if (low >= high) {
            return;
        }

        int middle = (low + high) / 2;
        mergeSort_srt(array, low, middle);
        mergeSort_srt(array, middle + 1, high);
        int end_low = middle;
        int start_high = middle + 1;
        while ((lo <= end_low) && (start_high <= high)) {
            if (array[low] < array[start_high]) {
                low++;
            } else {
                int Temp = array[start_high];
                for (int k = start_high - 1; k >= low; k--) {
                    array[k + 1] = array[k];
                }
                array[low] = Temp;
                low++;
                end_low++;
                start_high++;
            }
        }
    }

    public static void main(String... str) {
        String nthElement = "2";
        int[] intArray = { 1, 9, 5, 7, 2, 5 };

        FindLargest.nthLargeNumber(intArray, nthElement);
    }
}

Answer 1

这里您唯一的问题是您不了解如何进行时间分析。如果你有一个需要 O(n) 的例程和一个需要 O(n*log(n)) 的例程，那么同时运行这两个例程总共需要 O(n*log(n))。因此，您的代码可以按照您的意愿在 O(n*log(n)) 中运行。

正式做事，我们会注意到O()的定义如下: f(x) ∈ O(g(x)) 当且仅当存在值 c > 0 和 y 使得 f(x) < cg(x) 只要 x > y。

您的合并排序在 O(n*log(n)) 中，这告诉我们当 n > y1 对于某些 c1,y1 时，它的运行时间受 c1*n*log(n) 限制。您的重复消除在 O(n) 中，它告诉我们当 n > y2 对于某些 c2 和 y2 时，它的运行时间受 c2*n 限制。由此可知，当n > max(y1,y2)时，两者的总运行时间受c1*n*log(n)+c2*n的限制。我们知道 c1*n*log(n)+c2*n < c1*n*log(n)+c2*n*log(n) 因为 log(n) > 1，这当然可以简化为 (c1 +c2)*n*log(n)。因此，我们可以知道当 n > max(y1,y2) 时，两者的运行时间一起受 (c1+c2)*n*log(n) 限制，因此，使用 c1+c2 作为我们的 c 和 max (y1,y2)作为我们的y，我们知道两者加在一起的运行时间是O(n*log(n))。

通俗地说，你可以只知道增长速度更快的函数总是占主导地位，所以如果一段代码是 O(n)，第二段是 O(n^2)，那么组合就是 O(n^2)。如果一个是 O(log(n))，第二个是 O(n)，则组合是 O(n)。如果一个是 O(n^20)，第二个是 O(n^19.99)，则组合是 O(n^20)。如果一个是O(n^2000)，第二个是O(2^n)，那么组合就是O(2^n)。