javascript - 我在网上发现的该函数的时间复杂度为O(n)吗？

我正在尝试做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）解决方案，因为最坏的情况是我们遍历整个数组，但是我不确定。

最佳答案

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

我估计此函数的运行时间为O(n*lgn)，这对于分而治之算法是典型的。每个调用确实可以执行O(n)，并且通常会有O(lgn)个递归调用。