4个数之和的时间复杂度

Question

4个数之和的时间复杂度

3

这里是典型的4数之和问题。
给定一个由n个整数组成的数组S，是否存在元素a、b、c和d在S中使得a+b+c+d=target？找到数组中所有唯一的四元组，它们的和为target。

我知道的一种解决方案需要O(n^3)时间。但是当我分析最小时间复杂度时，我被这句话困惑了：“由于有O(n^4)种4个数字的组合，在最坏情况下，它们可能全部加起来等于目标数字，因此我们至少要访问每个组合一次。因此，最小时间复杂度是O(n^4)。”

我知道这个陈述显然是错误的（毕竟存在O(n^3)的算法），但不知道为什么。

我知道这可能是一个愚蠢的问题……但我真的很困惑。有人能帮忙吗？提前感谢。

- Patrick

2

你不能从组合的数量推断出步骤的数量。如果这是真的，排序将需要O(n!)步骤。 - clemens

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Miljen Mikic · Accepted Answer

这是因为问题要求找出所有唯一的四个数字组合，使它们的总和为指定的值。让我们看看细节。如果引用的句子:

由于有O(n^4)种四个数字的组合，在最坏的情况下，它们可能全部加起来等于目标数字，因此我们必须至少遍历每个组合一次。因此，最小时间复杂度为O(n^4)。

是真的，那么类似的2-Sum问题的最小时间复杂度就应该是O(n^2)，对吗？然而，我们都知道这并不是正确的。这是因为我们不需要检查所有的对来找到所有唯一的对。假设相反，即所有的对都可以加起来等于指定的和，并且都是唯一的，所以我们需要检查它们所有。这意味着我们可以从数组中找到四个不同的整数a、b、c、d，使得a + b = s且c + d = s，同时a + c = s且b + d = s。这意味着2a + b + c = 2d + b + c或a = d，从而得到b = c。因此，(a,b) = (c,d)，因此所有对都是唯一的这个假设是错误的，存在矛盾。因此，如果我们处理了对(a,b)，我们可以跳过(c,d)，因为它们是相同的对。这就是4-Sum问题中O(n^3)复杂度算法所做的，它们在开始时利用这一事实对输入数组的元素进行排序或散列。可以在这里找到一些聪明的解决方案。