algorithm - 2-sum算法权重计算

Question

我开始学习有关算法的类(class)，并被 2-sum 算法 权重计算(以及 3-sum 等)所困。

有一个简单的 1-sum 示例:

int count = 0;
for (int i = 0; i < N; i++)
    if (a[i] == 0)
        count ++

其中 N 只是数字 - 精确值无关紧要。

还有下一个参数:

• 变量声明:2
• 赋值语句:2
• 小于比较:N + 1
• 等于比较:N
• 数组访问:N
• 增量:N 到 2N

等等-很清楚

但下一个是2-sum的例子:

int count = 0;
for (int i = 0; i < N; i++)
    for (int j = i; j < N; j++)
      if (a[i] + a[j] == 0)
          count ++

还有另外一个参数:

• 变量声明:N + 2
• 赋值语句:N + 2
• 小于比较:(1/2) (N + 1) (N + 2)
• 等于比较:(1/2) N (N - 1)
• 数组访问:N (N - 1)
• 增量:(1/2) N (N - 1) 到 N (N - 1)

前两个是明确的两个，但我无法理解最后一个操作的权重:“小于比较”和“等于比较”

对于“等于比较” N + 1 很清楚 - 它就像在 1-sum 循环中。

但是(1/2)(N + 2)是什么？

Answer 1

您似乎想要计算实现执行小于比较的次数(这是我对“小于比较”的含义的猜测)。

计算基于1-sum变体；你说的很清楚，但让我先解释一下。

for (int i = 0; i < N; i++)
    ...

此循环执行以下比较:

Compare 0 with N
Compare 1 with N
Compare 2 with N
...
Compare N-1 with N
Compare N with N

总计:N+1 次比较。所以现在我们知道比较次数比迭代次数多 1。

现在对于 2-sum 变体:

for (int i = 0; i < N; i++)
    for (int j = i; j < N; j++)

内部循环执行 N-i 次迭代，因此它对每个 i 进行 N-i+1 比较。外循环执行 N 次迭代，因此它进行 N+1 比较。所以总的比较次数可以描述如下:

• 外层循环N+1次比较
• i=0 的内循环的 N+1 比较
• i=1 的内循环的 N 次比较
• i=2 的内循环的 N-1 次比较
• ...
• i=N-1 的内部循环的 2 次比较

所有这些数字构成一个连续数字序列(您可以将 N+1 和 2 替换为 N+2 和 1)，其总和很容易计算。

好吧，它实际上是 1/2*(N+3)(N+2)。