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

Question

我试图找到等于给定数字的子集(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;
}

Answer 1

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

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

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

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(N³) 降低到 O(N² Log N)。