我正在做这个叫做4sum的问题。链接到问题
给定一个n个数字和一个整数的数组(这是目标)元素)。计算四元组的总数(集合为4)从这n个数字中选择不同的数字)四元元素的和等于目标元素。
我写这段代码的蛮力方法。据我所知，大0时间复杂度是——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)。
if (a[i]+a[j]+a[k]+a[l]==target) {
s.insert({a[i], a[j], a[k], a[l]});
}
执行O(N^4)次。
为了得到上界，我们假设我们检查的每个四元组都满足条件。
正确的。
对于N^4个插入——复杂度为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而不是std::set的建议，这确实会将循环体的O(1)常量更改为更好的常量，但不会改变整体复杂性，它仍然是O(N^4)。
O(N^4 log(N))的复杂性，正如OP所建议的那样是std::multi_set，因为在这种情况下，每次插入都会导致multiset的大小增加。