1

给定一个整数数组[a1 a2 ... an]，不一定是不同的，给出一个算法，如果有不同的索引i,j,k，则返回“是”，否则返回“否” ai + aj = ak。

有没有办法比蛮力更快地做到这一点，这需要 O(n^3)？

4

4 回答 4

2

就在这里。

第一步：对数组进行排序。

然后你以一种聪明的方式浏览你的索引。一个聪明的方法可能是选择

  • a0 + a1
  • a0 + a2
  • a0 + a3
  • ...
  • a0 + a(n-1)
  • a1 + a(n-1)
  • a1 + a(n-2)

这里的聪明意味着两对连续的测试指数不能彼此相距太远。

对于第一个，您aO + a1会发现在.ka0 + a1 = akO(logn)

对于以下的，假设被测试的对接近前一个，这意味着如果有一个k'这样的，ai + aj = ak'那么k'一定是接近的k。您可能可以摆脱线性搜索，k直到您的k'匹配或变得太大/太小ai + aj。在一般情况下，这是成本O(1)。

由于您最多必须测试n^2对，因此整个算法是O(n^2).

于 2012-11-02T16:18:05.510 回答
1

  • 建立所有可能和 ai + aj 的列表：O(n^2)。
    该列表将具有 size=n^2

  • 然后将该列表与数组进行比较，看看是否有任何相似之处：

    • 首先对每个列表进行排序： O((n^2)log(n^2)) + O(nlogn)
    • 遍历它们以找到任何匹配项：O(n^2)

总计：O((n^2)log(n^2))（= O((n^2)log(n)) 每条来自alestanis 的评论）

编辑：我忘记了不同的要求，但这不应该改变结果。
首先，为了确保 i!=j，在步骤 1 中构建所有和的列表时只排除 i==j。
其次，为了确保 i!=k 和 j!=k，用其索引 i,j 标记每个和，并在排序前用索引 k 标记每个原始值。
然后在最后一步找到任何匹配项时，检查标记的索引是否不同。

于 2012-11-02T16:18:47.517 回答
0

下面的python代码实现了一个类似于alestanis所说的方法，也类似于Daniel Le提到的维基百科文章中给出的二次算法。对于大的均匀随机正整数，所述的 O(n^2) 复杂度似乎成立。（平均而言，增加 k 的内部搜索循环执行大约 (n^2)/4 次。）在旧 AMD Athlon 5000 处理器上的 linux 下运行的定时样本的输出首先出现，然后是代码。

0.002519    N 50    NN 2500     ops 607     NN/ops 4.1186   NN/t 992405.8   Matches 0
0.00752     N 100   NN 10000    ops 1902    NN/ops 5.2576   NN/t 1329794.2  Matches 0
0.035443    N 200   NN 40000    ops 10648   NN/ops 3.7566   NN/t 1128570.5  Matches 2
0.063056    N 400   NN 160000   ops 37403   NN/ops 4.2777   NN/t 2537427.4  Matches 33
0.176328    N 800   NN 640000   ops 163247  NN/ops 3.9204   NN/t 3629595.6  Matches 244
0.729919    N 1600  NN 2560000  ops 658122  NN/ops 3.8899   NN/t 3507238.7  Matches 2062
2.720713    N 3200  NN 10240000     ops 2535751     NN/ops 4.0383   NN/t 3763719.4  Matches 16178
11.07818    N 6400  NN 40960000     ops 10160769    NN/ops 4.0312   NN/t 3697358.2  Matches 128793

import random, bisect, time
V, W, N, Nlim = 500, 500000, 50, 6400
while N <= Nlim:
    t0 = time.time()
    U=sorted([random.randint(V,V+W) for i in range(N)])
    bigsum = U[-1]
    U.append(N*W)
    matches = ops = 0
    for i, ai in enumerate(U[:-2]):
        k = bisect.bisect_right(U, ai+U[i+1])
        for j, aj in enumerate(U[i+1:-1]):
            while ai+aj > U[k]:
                k += 1
                ops += 1
            if U[k] == ai+aj:
                #print 'Match', i, j, k, ai, aj, ai+aj, U[k]
                matches += 1
            if ai+aj > bigsum:
                break
    et = time.time() - t0
    print round(et,6), '\tN',N, '\tNN', N*N, '\tops', ops, '\tNN/ops',
    print round(float(N*N)/ops,4), '\tNN/t', round(N*N/et,1), '\tMatches', matches
    N *= 2

代码可能应该按照维基百科的大纲重写；重写可能会清除一些尴尬的数组切片编号和无关的完成检查。

于 2012-11-02T17:48:13.607 回答
0 
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

bool SUM3(vector<int> &v)
{
  sort(v.begin(), v.end());

  for (int i = 0; i < v.size(); ++i) {
    int j = 0, k = v.size() - 1;

    while (j < k) {
      int result = v[j] + v[k] - v[i];

      if (result < 0 || i == j) ++j;
      else if (result > 0) --k;
      else return true;
    }
  }

  return false;
}

int main()
{
  int a1[] = {25, 7, 9, 2, 4, 8, 10};
  vector<int> v1(a1, a1 + sizeof a1 / sizeof a1[0]);

  printf("%s\n", SUM3(v1) ? "true" : "false");

  int a2[] = {1, 2, 4};
  vector<int> v2(a2, a2 + sizeof a2 / sizeof a2[0]);

  printf("%s\n", SUM3(v2) ? "true" : "false");
  return 0;
}

该算法的复杂度为 O(n^2)。

于 2012-11-02T18:00:50.653 回答