算法渐近分析正确性验证：子集唯一元素计数的时间复杂度

给定超集S和其子集集合，需要统计每个子集仅在自身出现的元素数量。问题示例如下：

const complete_set = ["apple", "ball", "cat", "car", "rocket", "house"];

const example_problem_set: OverlappingSetsByKey = {
    key1: ["apple", "ball", "cat"], // 独有元素数量 = 0
    key2: ["apple", "ball", "cat", "car"], // 独有元素数量 = 1（仅car）
    key3: ["rocket", "house"], // 独有元素数量 = 2（rocket和house）
}

const example_response: OverlappingSetsResponse = {
    key1: 0,
    key2: 1,
    key3: 2,
}

我的TypeScript实现 #

function getNumberOfUniqueItems(osk: OverlappingSetsByKey): OverlappingSetsResponse {
    let res = {} as OverlappingSetsResponse;

    for (let key of Object.keys(osk)) { // 执行k次，k为子集数量
        // 1. 构建包含所有其他子集元素的数组
        let otherIds:string[] = [];
        for (let innerKey of Object.keys(osk)) { // 执行k次
            if (innerKey == key) continue; // 跳过当前子集
            let innerIds = osk[innerKey];
            for (let id of innerIds) { // 执行i次，i为超集大小
                if (!otherIds.includes(id)) otherIds.push(id);
            }
        }

        // 2. 过滤出当前子集不在otherIds中的元素
        let uniqueValues:string[] = osk[key].filter(id => !otherIds.includes(id));
        
        // 3. 存储独有的元素数量
        res[key] = uniqueValues.length;
    }

    return res;
}

复杂度分析疑问与解答 #

疑问点 #

我最初分析得出时间复杂度为O(n²)，但考虑到算法有三层嵌套循环，且问题规模由子集数量k和超集大小i共同决定，我倾向于用多元大O表示O(i*k²)。需要验证：

1. 这个复杂度分析是否正确？
2. 能否用多变量描述大O复杂度？

解答 #

1. 复杂度分析的正确性

你的多元复杂度思路是对的，但需要考虑数组includes操作的性能：

• 数组的includes是线性查找，时间复杂度为O(m)（m为数组当前长度，最坏情况下等于超集大小i）。
• 按照你当前的实现，构建otherIds时，每个元素的检查需要O(i)时间，这部分总时间为O(kii)；过滤当前子集时，每个元素的检查同样是O(i)，总时间为O(ii)。因此单次外层循环的时间是O(ki²)，外层循环执行k次，最终时间复杂度为O(k²*i²)。

如果要优化到你预想的O(k²i)，只需要把otherIds从数组换成Set：Set的has操作是O(1)，这样构建otherIds和过滤的时间都会降为线性，最终总时间就是O(k²i)，符合你的初始预期。

2. 多变量大O表示的合理性

完全可以用多变量描述大O复杂度，这是算法分析中的标准做法。当问题的性能由多个独立的规模参数（比如本题的子集数量k和超集大小i）共同决定时，用多变量的大O表示能更精准地反映算法的性能特征，比笼统的O(n²)更有参考价值。

内容的提问来源于stack exchange，提问作者Philip Grabenhorst