gpt4 book ai didi

C - 子集之和,需要更快的算法

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:56:51 25 4
gpt4 key购买 nike

我试图找到等于给定数字的子集(1-3 长度)的总和。我写了这个算法,它工作正常,但太慢了。我如何更改此算法以使其更快?

int PrintCombinations(int * array, int userLenght) {
int total = 0;

for (int i = 0; i < GetArrayLenght(array); ++i) {
if(userLenght == array[i]) {
printf("%d = %d\n", userLenght, array[i]);
++total;
}
}

for (int j = 0; j < GetArrayLenght(array); ++j) {
for (int k = j; k < GetArrayLenght(array); ++k) {
if(array[j] + array[k] == userLenght) {
printf("%d = %d + %d\n", userLenght, array[j], array[k]);
++total;
}
}
}

for (int l = 0; l < GetArrayLenght(array); ++l) {
for (int i = l; i < GetArrayLenght(array); ++i) {
for (int j = i; j < GetArrayLenght(array); ++j) {
if(array[l] + array[i] + array[j] == userLenght) {
printf("%d = %d + %d + %d\n", userLenght, array[j], array[l], array[i]);
++total;
}
}
}
}

return total;
}

最佳答案

您应该在循环之前计算一次数组的长度。目前它在每个循环的每次迭代中重新计算。如果此操作开销很大,将计算移出循环将是优化代码的一种非常有效的方法。

例如,如果 GetArrayLenght() 扫描数组以寻找终止值,将调用移出循环会使时间复杂度从 O(N4)O(N3)

第二步是以不同方式嵌套循环,避免搜索是否已经超出了总和的长度(假设所有长度 都是正数)。这不会改变时间复杂度,但仍然可以显着减少测试次数:

int PrintCombinations(int *array, int userLength) {
int total = 0;
int length = GetArrayLenght(array);

for (int l = 0; l < length; ++l) {
if (array[l] > userLength)
continue;

if (array[l] == userLength) {
printf("%d = %d\n", userLength, array[l]);
++total;
}
for (int i = l; i < length; ++i) {
if (array[l] + array[i] > userLength)
continue;

if (array[l] + array[i] == userLength) {
printf("%d = %d + %d\n", userLength, array[l], array[i]);
++total;
}
for (int j = i; j < length; ++j) {
if (array[l] + array[i] + array[j] == userLength) {
printf("%d = %d + %d + %d\n",
userLength, array[j], array[l], array[i]);
++total;
}
}
}
}
return total;
}

如果你的数组非常大,并且你可以修改它或复制它,按递增顺序排序将减少比较次数,最后一个循环使用二进制搜索将节省时间复杂度从 O(N3) 降低到 O(N2 Log N)

关于C - 子集之和,需要更快的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/40915229/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com