我是否正确地执行了此算法的渐近分析，该算法标识了子集集合中每个的唯一键的数量？

问：

所以，我最近在一次采访中遇到了这个问题，这让我有点烦恼。我从事编程工作已经很多年了，但像许多自学成才的人一样，这种力量（渐近分析的力量）对我来说并不强。我想知道我是否正确地识别了我的解决方案运行时的 big-Oh 表示法，但有一些注意事项。该问题实质上是确定超集的元素何时在提供的子集集合之一中仅出现一次。目标是，对于每个子集，计算此类唯一出现的次数。我们可以这样建模：Ss

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

const example_problem_set: OverlappingSetsByKey = {
    key1: ["apple", "ball", "cat"], // unique = 0
    key2: ["apple", "ball", "cat", "car"], // unique = 1 - car
    key3: ["rocket", "house"], // unique = 2 - rocket and house
}

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

这是我的解决方案（在打字稿中）：

function getNumberOfUniqueItems(osk: OverlappingSetsByKey): OverlappingSetsResponse {

    let res = {} as OverlappingSetsResponse;

    for (let key of Object.keys(osk)) { // runs k times
        // 1. 
        // construct an array of ids that represent all *other* ids 
        let otherIds:string[] = [];
        for (let innerKey of Object.keys(osk)) { // runs k times
            if (innerKey == key) continue; // skip the current key
            let innerIds = osk[innerKey];
            for (let id of innerIds) // runs i times
                if (!otherIds.includes(id)) otherIds.push(id);
        }

        // 2. 
        // filter values from osk[key] that are in the shared array
        let uniqueValues:string[] = osk[key].filter(id => !otherIds.includes(id)); // at least i times
        
        // 3. 
        // store just the length in res
        res[key] = uniqueValues.length;
    }

    return res;
}

对于与语言无关的描述：

• 对于每个子集s
  • 创建一个新列表，表示在所有其他子集中找到的 IDL
  • 遍历其他每个子集s'
    • 遍历s'
      • 将该值添加到 中，如果尚不存在L
  • 筛选，使其仅包含未在sL
  • 返回筛选后的长度s

鉴于上面的注释，我的渐近分析大致如下：

1. 外部循环运行时间，用于按键kk
2. 第一个内部循环为每个键运行时间，k
3. 第二个内部循环运行时间，其中是超集的大小ii
4. 过滤器操作必须运行大约几次，尽管我不确定 和 的性能，但我愿意打赌此操作是 .ifilterincludesi**2

这让我想到了...... 或。。。k + k*i + k+k + k*k+i(i)k^2 + k^2 + ki + k

如果键的数量（不同的子集）是问题的大小，那么它就会变得简单明了，因为该项将超过其他项，并且我们忽略了乘法常量，所以我将删除 .f(n) = O(n^2)k^2i

我对此不满意，原因有两个：

1. 我有嵌套的循环，所以直觉上感觉不合适。同样，这是我依靠我对代码的直觉阅读。depth=3O(n^2)
2. 问题的规模没有很好地描述。事实上，这似乎是一个多维问题大小，由 （1） 超集的大小和 （2） 我们正在比较的子集的数量定义。k

以上让我在描述它的资源消耗时想说。可以在 big-Oh 表示法中使用多元表达式吗？您能否有多种因素导致 ，以不同的方式影响其运行时？如果我的符号是正确的，为什么在这种情况下不忽略低阶项？f(k, i) = O(i * k^2)n