我从下面的代码中得到了所有唯一的三元组，但我想减少它的时间复杂性它由三个for循环组成。所以我的问题是：是否有可能在最少的循环数量内降低其时间复杂性？
提前谢谢。让我知道。
#include <cstdlib>
#include<iostream>
using namespace std;
void Triplet(int[], int, int);
void Triplet(int array[], int n, int sum)
{
// Fix the first element and find other two
for (int i = 0; i < n-2; i++)
{
// Fix the second element and find one
for (int j = i+1; j < n-1; j++)
{
// Fix the third element
for (int k = j+1; k < n; k++)
if (array[i] + array[j] + array[k] == sum)
cout << "Result :t" << array[i] << " + " << array[j] << " + " << array[k]<<" = " << sum << endl;
}
}
}
int main()
{
int A[] = {-10,-20,30,-5,25,15,-2,12};
int sum = 0;
int arr_size = sizeof(A)/sizeof(A[0]);
cout<<"********************O(N^3) Time Complexity*****************************"<<endl;
Triplet(A,arr_size,sum);
return 0;
}
我不是算法专家，但我认为让你的程序变得更好的一种方法是在你的third loop上为这个值做一个binary search，这个值会给你和前面的两个值。然而，这需要您的数据预先为sorted，以使其正常工作（这显然会有一些开销，具体取决于您的sorting algorithm（std::sort的平均时间复杂度为O (n log n)））。
如果你想利用并行编程，让你的程序在多个线程上运行，你总是可以的，但这可能会变得非常混乱。
除了这些建议，很难想出更好的方法。
如果您首先对列表进行排序，然后对第三个值进行二进制搜索，您可以很容易地获得O(n^2*logn)的稍微好一点的复杂性。排序采用O(nlogn)并且三元组搜索采用O(n^2)来对存在于O(logn)的时间的所有可能的对进行计数，用于对总共O(nlogn + n^2logn)或简单地O(n^2*logn)的三元组值进行二进制搜索。
对于二进制搜索，你可能还可以做一些其他有趣的事情来减少这种情况，但我很难（在凌晨4点）看到比这更好的东西。
当一个三元组求和为零时，第三个数完全由两个第一个数决定。因此，你只能在每个三元组中自由选择两个数字。对于n可能的数，这产生最大n2三元组。
我怀疑，但我不确定，这是你能做的最好的复杂度。我不清楚，对于一个有符号整数的随机序列，和到零三元组的数量是否一定是n2的数量级。如果它不太可能（不太可能，但如果），那么它可能会做得更好。
无论如何，一个复杂度为n2的简单方法是首先扫描数字，将它们存储在具有恒定时间查找的数据结构中（C++标准库提供了这样的功能）。然后像发布的代码一样扫描数组，只在三元组的第一个和第二个数字上有所不同。对于第三个数字，在已经建立的恒定时间查找数据结构中查找：如果它在那里，那么你就有一个潜在的新三元组，否则就没有。
对于这样找到的每个零和三元组，也将其放入恒定时间查找结构中。
这确保了唯一性准则没有额外的复杂性。
在最坏的情况下，在一个大小为n的数组中，有C（n，3）个和为零的三元组。一般来说，你不能得到比三次复杂度更好的东西。