javascript - 我在网上找到的这个函数的时间复杂度是O(n)吗？

Question

我正在尝试做this problem on LeetCode ，以下是我在网上找到的解决方案:

//  use quick select
var findKthLargest = function(nums, k) {
    var smaller = [];
    var larger = [];
    var pivot = nums[parseInt(nums.length/2)];
    var pivotCnt = 0;

    for (var i = 0; i < nums.length; i++) {
        var num = nums[i];      
  
        if(num > pivot) {
            larger.push(num);
        }
        else if(num < pivot) {
            smaller.push(num);
        }
        else {
            pivotCnt++;
        }
    }
  
    if (k <= larger.length) { // if larger includes k
        return findKthLargest(larger, k);
    }
    else if (k - larger.length - pivotCnt <= 0) { // k is part of pivot
        return pivot;
    }
    else { // if smaller inclues k
        return findKthLargest(smaller, k - larger.length - pivotCnt);
    }
};

现在我相信这是一个 O(n) 解决方案，因为最坏的情况是我们迭代整个数组，但我不确定。

Answer 1

您的函数似乎正在使用某种分而治之的方法。对于每次调用，它都会对输入数组进行一次O(n) 传递，将大于和小于某个主元的值存储到两个单独的数组中。然后，它对适当的子数组进行递归调用。在平均情况下，它将把输入数组的大小除以二，直到仅对大小为 1 的数组进行递归调用，这是基本情况。

我估计这个函数的运行时间是O(n*lgn)，这对于分而治之算法来说是典型的。每次调用的时间复杂度为 O(n)，并且通常会有 O(lgn) 次递归调用。