计算 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);
}

Answer 1

O(n( 正确吗？

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

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

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