我正在使用数据结构学习优化问题。
为此,我考虑了一个手头的问题。
我有一个这样的数组:movies[] = { 2,3,4,5,6,7,2,4,9 }
我有一个总值:k = 5
现在我找到了返回"k"
的数组元素的组合例如:
2 + 3 = 5
3 + 2 = 5
下面的代码能够做到这一点:
#include<iostream>
#include<tuple>
using namespace std;
std::tuple<int, int> movies_combo(int k,int movies[]) {
int value_1 = 0, value_2 = 0;
int size = sizeof(movies);
//First lets sort the array in ascending order
//For optimized solution
double mid = sizeof(movies) / 2;
//Second lets find the sum of combination of array elements which gives "k"
for (int i = 0; i < (size-1); i++) {
for (int j = 0; j < (size - 1); j++) {
if (movies[i] + movies[j] == k) {
cout << "The two movies are: " << movies[i] << "and" << movies[j] << endl;
}
}
}
return make_tuple(value_1, value_2);
}
int main() {
int movies[] = { 2,3,4,5,6,7,2,4,9 };
int k = 6;
int value_1, value_2;
tie(value_1,value_2) = movies_combo(k, movies);
//cout << "The two movies are: " << value_1 << "and" << value_2 << endl;
}
现在我有了 O(n^2( 的时间复杂度。
我可以通过在开始时对数组进行排序并消除 k>值来进一步降低复杂性。但这仅在几种情况下有用,而不是一般的优化解决方案。
我希望有数据结构和算法方法在这种情况下非常方便,可以降低对数级示例的复杂性:nlogn 或 logn。
如果有人对降低时间复杂度有任何想法,请告诉我。
你可以及时做到这一点 O(nlogn( 甚至更好的 O(n(。
O(nlogn( 方法:
1.按时间 O(nlogn( 时间对元素进行排序。
2.对于movies[i]
的每个元素,在数组中应用从位置i+1
到数组末尾的二叉搜索来搜索元素k - movies[i]
。
3.如果找到,则自movies[i] + (k - movies[i]) = k
以来,您拥有元组
O(n( 方法:
1.将所有元素存储在哈希表中。
2.对于每个元素movies[i]
,在哈希表中搜索k - movies[i]
,如果找到你拥有元组。
3.由于在哈希表中搜索需要 O(1( 时间,因此这种方法需要时间 O(n(。