寻找一个简单函数的时间复杂度

Question

我正在努力思考 Big O。我已经编写了两个版本的函数来查找数组中的“多数元素”（即出现次数超过 n/2 次的元素，其中 n是数组的长度）。例如，如果输入数组为 [2,2,1,1,1,2,2]，则结果为 2。我的问题是：

版本 1 是最坏情况 O(n^2) 吗？ [我认为这是因为 countInstances 可能是 O(n) 并且 main 函数最终可能会调用它 n 次]
版本 2 是 O(n) 吗？ [这可能与使用地图有关，但我不是100%清楚]

任何澄清将不胜感激！

版本 1

function countInstances(arr, instance) {
    return arr.filter((el)=>el===instance).length
}


function MajorityElement(arr){
    let uniques = new Set(arr)
    let threshold = Math.floor(arr.length/2)
    for (el of uniques){
        if (countInstances(arr, el)>threshold){
            return el
        }
    }
    return null
}

版本 2

function getFrequencies(arr){
    let freqs = new Map
    for (el of arr){
        if (freqs.has(el)){
            freqs.set(el, freqs.get(el)+1)
        } else{
            freqs.set(el,1)
        }   
    }
    return freqs
}

function majorityElement(arr){
    let freqMap = getFrequencies(arr)
    let n = Math.floor(arr.length/2)
    
    for (let key of freqMap.keys()) {
        if (freqMap.get(key)>n){
            return key
        }
    }
    return null

}

Answer 1

你是对的。 .filter 将始终遍历数组的每个元素，因此如果回调是 O(1)（在本例中是），则 .filter 操作是 O(n)。 countInstances 是 O(n).

您在循环中调用 countInstances：

for (el of uniques){
    if (countInstances(arr, el)>threshold){

添加另一个维度，所以你得到 O(n ^ 2)。

在第二个代码中，没有嵌套循环。唯一的循环是：

function getFrequencies(arr){
    let freqs = new Map
    for (el of arr){
        // linear operations

和

for (let key of freqMap.keys()) {
    // linear operations

所以是 O(n)。

寻找一个简单函数的时间复杂度

Finding time complexity of a simple function

javascript

algorithm

big-o