我从下面的代码中获得了所有唯一的三元组，但是我想减少它的时间复杂性。它由三个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;
}
我不是算法的专家，但是我可以看到使您的程序更好的一种方法是binary search对您third loop的值进行求和，以便将您的总和与之前的两个值结合起来。但是，这要求您sorted事先准备好数据以使其正常工作（显然，这取决于您的开销sorting algorithm（std::sort平均时间复杂度为O (n log n)））。
如果您想利用并行编程并让您的程序在多个线程中运行，则始终可以，但是这样做可能会很混乱。
除了这些建议之外，很难想到一种更好的方法。
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句