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

Question

所以，我最近在采访中遇到了这个问题，这让我有点困扰。我已经编程多年了，但像许多自学成才的人一样，我的力量（渐近分析的力量）并不强大。我想知道我是否正确识别了解决方案运行时的大哦符号，但有一些警告。该问题本质上是确定超集

S

的元素何时在提供的子集

s

的集合中仅出现一次的问题。他们的目标是，对于每个子集，计算此类独特出现的数量。我们可以这样建模：

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

  • 创建一个新列表

    L

    ，代表在每个other子集中找到的id
  • 迭代所有其他子集

    s'

    • 迭代

      s'

      中的每个值
      • 将该值添加到

        L

        （如果尚未存在）
  • 过滤

    s

    ，使其仅包含

    L

  中未找到的值
  • 返回过滤后的长度

    s

鉴于上面的注释，我的渐近分析是这样的：

1. 对于

   k

   键

   ，外循环运行 

   k
次
2. 第一个内部循环为每个键运行

   k

   次，
3. 第二个内部循环运行

   i

   次，其中

   i

   是超集的大小
4. 过滤器操作必须运行大约

   i

   次，虽然我不确定

   filter

   和

   includes

   的性能，但我愿意打赌这个操作是

   i**2

   。

这让我...

k + k*i + k+k + k*k+i

或者...

(i)k^2 + k^2 + ki + k

如果键（不同子集）的数量是问题的大小，则将使其变得

f(n) = O(n^2)

，简单明了，因为

k^2

项将超过其他项，并且我们忽略乘法常数，所以我'我会放下

i

。

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

1. 我有

   depth=3

   的嵌套循环，所以直观上，

   O(n^2)

   感觉 不合适。再说一遍，这是我依靠对代码的直觉阅读。
2. k 没有很好地描述问题的

   规模

   。事实上，这似乎是一个多维问题的大小，由 (1) 超集的大小和 (2) 我们要比较的子集的数量定义。

以上让我在描述其资源消耗时想说

f(k, i) = O(i * k^2)

。可以在大哦表示法中使用多元表达式吗？是否有多个因素会影响

n

，并以不同方式影响其运行时间？如果我的符号是正确的，为什么在这种情况下不忽略低阶项？

Answer 1

假设整套有

n

项。对于复杂性分析，除非我们有特殊的、已知的限制，否则我们会为每个列表/集合取最大可能值。这意味着

OverlappingSetsByKey

中的每个子集也可以有

n

项。您已使用

k

表示

OverlappingSetsByKey

中的子集数量。

到目前为止，我们已经

O(k^2)

：

for (let key of Object.keys(osk))
  for (let innerKey of Object.keys(osk))

让我们添加子集逻辑，

O(n^2 + n^2)

:

...
  ...
    // There can be n items in a subset
    for (let id of osk[innerKey])
      // `includes` can iterate over n items
      if (!otherIds.includes(id)) {
        otherIds.push(id);
      }
      
    // The subset can contain n items
    osk[key].filter(id =>
      // `includes` can iterate over n items
      !otherIds.includes(id));

大家一起

O(k^2 * n^2)

。