4sum 问题的大 O 时间复杂度。蛮力方法

Question

我正在做这个叫做 4sum 的问题。 Link to problem.

Given an array of n numbers and an integer(this is the target element). Calculate the total number of quads (collection of 4 distinct numbers chosen from these n numbers) are there for which the sum of quad elements will add up to the target element.

我写这段代码是为了暴力破解。根据我的说法，big-o 时间复杂度是 --- n^4 log (n^4)。我已经在下面给出了原因。虽然复杂度应该只有 n^4。请帮助我了解我缺少什么。

set<vector<int>>s;
for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
        for (int k = j + 1; k < n; k++) {
            for(int l = k + 1; l < n; l++) {
                if (a[i]+a[j]+a[k]+a[l]==target) {
                    s.insert({a[i], a[j], a[k], a[l]});
                }
            }
        }
    }
}

逻辑是生成所有可能的四边形（具有不同的元素），然后对于每个四边形检查四边形元素的总和是否等于目标。如果是，则将四边形插入集合中。

现在，我们不知道有多少四边形会符合这个条件，因为这完全取决于输入。但是为了获得上限，我们假设我们检查的每个四边形都满足条件。因此，集合中总共有 N^4 个插入。对于 N^4 插入 --- 复杂度为 N^4 log(N^4).

Answer 1

  if (a[i]+a[j]+a[k]+a[l]==target) {
    s.insert({a[i], a[j], a[k], a[l]});
  }

确实执行了 O(N^4) 次。

to get the upper bound we assume that every quad that we check satisfies the condition.

正确。

For N^4 insertions --- complexity is N^4 log(N^4).

不是这样，因为 N^4 插入不一定会产生包含 N^4 个元素的集合。

插入的成本是 O(log(s.size())。但是 s.size() 的上限是 K 的不同方式的数量，其中 target 可以表示为给定范围内的 4 个整数之和，因此最坏情况下的成本是 O(log(K))。虽然 K 可以是一个很大的数字，但它不取决于 N，因此就 N 的复杂性而言，这很重要作为常数时间 O(1)，因此整体复杂度仍然是 O(N^4)·O(1) = O(N^4).

[ EDIT ] 关于@MysteriousUser 使用 std::unordered_set instead of std::set 的建议，确实会将循环体的 O(1) 常量更改为更好的常量，但不会改变整体复杂度，它仍然是 O(N^4).

另一个会的选项实际上增加了OP提议的O(N^4 log(N))的复杂性std::multi_set，因为在那种情况下每次插入会导致多重集的大小增加。

4sum 问题的大 O 时间复杂度。蛮力方法

Big-O time complexity of 4sum problem. Brute force approach

c++

algorithm

stl

set

time-complexity