二和算法复杂度

Question

下面的代码检查数组中任何一对数字的总和是否为零。我正在尝试通过考虑变量声明、赋值、比较、递增、数组访问等主要操作的次数来计算复杂度。通常复杂度为 O(N^2)，但当我必须考虑上面指定的操作。我该如何处理？

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

Answer 1

我将缩进代码并明确突出显示每个操作：

int count = 0; // <-- 1 operation

for(int i=0; i<N; i++) // <-- 2 operations per iteration
    for(int j=i+1; j<N; j++) // <-- 2 operations per iteration
        if(a[i] + a[j] == 0) // <-- 4 operations
            count++; // <-- impossible to tell without knowing a. Counting as 1 operation

计算操作总数的方法如下：

该表达式简化为：

这是你的答案。请注意，这是 O(N^2)，这与您之前的观察一致。

二和算法复杂度

two-sum algorithm complexity

algorithm

time-complexity