java - 第k大的时间复杂度

Question

所以我被要求找到数组中的第 k 个最大值。如标签所示，代码在 java 中。我不完全理解时间复杂度，听说这可以在 n 的 O 中完成。我想知道我的程序的时间复杂度是多少。

请注意，此方法确实找到了 (k+1) 个最大元素，这是有意为之的。

public static int kthLargest(int[] a, int k){
    int max = Integer.MAX_VALUE, curMax;

    for (int i = 0; i <= k; i++){ //Recurs k+1 times. 
        curMax = 0;

        //This loop just finds the max of the input array.
        //It also makes sure that the max it is finding is less 
        //than the previous max found.
        for (int j = 0; j < a.length; j++){ 
            int num = a[j];
            if (num > curMax && num < max){
                curMax = num;
            }
        }

        max = curMax;
    }
    return max;
}

请注意，我的猜测是 O of k*n，这将是 n^2 次迭代的最坏情况，但是有人告诉我 k 并不重要。

Answer 1

是的，您的算法是 O(k*n) 是正确的，并且有一个 O(n) 算法不是您的算法。

(听起来你的问题是家庭作业，所以我不清楚我应该给你最好的答案，但一个简单的解决方案可能是对数组进行排序并从末尾取出第 k 个元素。)