time-complexity - 计算 big-O 时如何处理本机函数的时间复杂度

Question

我正在学习时间复杂度，并注意到我看到的教程没有考虑本机函数的时间复杂度（本例中为 Javascript）

下面的函数删除数组中的重复值并返回排序后的数组，其时间复杂度为 O(n) 而不是 O(n + nlogn)。O(n) 是否正确？在计算时间复杂度时，我们是否应该考虑原生函数的时间复杂度？

function uniqueSort(arr) {
    const store = {};
    const result = [arr[0]];

    for(let i =0; i < arr.length; i++) {
        if(!store[arr[i]]) {
            result.push(arr[i]);
            store[arr[i]] = true;
        }
    }
    return result.sort((a,b) => a - b);
}

标签： time-complexitybig-o

Answer 1

O(n) 是否正确？

O(N) 不正确。当您评估函数的时间复杂度时，您必须逐行考虑函数中所有操作的时间复杂度——包括本机函数的时间复杂度。如果您所做的只是在您自己的函数内部调用各种本机函数（这可能非常昂贵！），那么调用函数 O(1) 没有多大意义。

您提供的函数片段将是 O(n + nlog(n))，因为存在遍历数组 (O(N)) 的操作以及使用 javascript 的本机函数 nlog(n) 进行排序的操作。

通常在 Big-O 表示法中，我们仅根据其最慢的操作对函数进行分类，因此您也可以将函数描述为 O(nlogn)。