三和算法的时间复杂度是多少？
三和算法的时间复杂度是多少？
提问于 2019-10-04 17:35:36
它是一个函数，用于在数组中查找三个数字，即谁的sum等于零。
//helper function
bool isPresent(int*arr, int size, int index, int num)
{
for (int i = index; i < size; i++)
{
if (arr[i] == num)
return true;
}
return false;
}
bool threesum(int*arr,int size)
{
int i = 0, j = 1;
int sum = arr[i] + arr[j];
while (i < size-2)
{
if (isPresent(arr, size, j + 1, -sum) == true)
{
cout << arr[i] << " + " << arr[j] << " + " << -sum << '\n';
return true;
}
if (j == size)
{
i++;
j = i + 1;
}
j++;
sum = arr[i] + arr[j];
}
return false;
}threeSum函数有两个循环，一个是循环，第二个是isPresent循环，其时间复杂度为O(n)，因此三和函数的时间复杂度应该是O(n^2)，但是由于j的缘故循环迭代次数较多，那么三和函数的时间复杂度是O(n^2)还是O(n^3)？
回答 2
Stack Overflow用户
发布于 2019-10-04 18:00:20
它是O(n^3)。想想我是如何随着j变化的。假设n= 10。一开始i= 0，j= 1。我不会变成1，直到j= 10，然后在这些步骤之后，i= 1，j= 2。这就像这样写了两个for循环：
for(int i = 0; i < n; i++)
for(int j = i+1; j < n; j++)Stack Overflow用户
发布于 2019-10-04 18:17:47
天真的方法是O(N³)。
为了查看哪三个和是0，计算所有和，有N* (N-1) * (N-2) /4个不同的和。
但是，您可以很容易地改进这个界限，首先对数字进行索引，然后计算所有配对的和，将它们存储在哈希表中，然后查找是否存在和的负数，并测试其组件是否尚未用于计算和。这将得到O(N²)。
https://en.wikipedia.org/wiki/3SUM
bool threesum(const vector<int>& numbers){
std::unordered_map<int,size_t> index;
for (size_t i=0;i!=numbers.size();++i) {
index.insert({numbers[i],i});
}
for (size_t i=0;i!=numbers.size();++i) {
for (size_t j=i+1;j!=numbers.size();++j) {
const int n = -(numbers[i]+numbers[j]);
if (index.count(n)) {
if (index[n]==i) continue;
if (index[n]==j) continue;
return true;
}
}
}
return false;
}页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/58233696
复制相关文章
相似问题
腾讯云开发者
