IF 语句中的原始操作数

Question

我是算法设计与分析的新手。我有一个嵌套循环并且 if statement.I 无法确定在 if 语句中完成的原始操作。声明如下：

for (i=0;i<n;i++)
 for(j=0;j<n;j++)
   if(i!=j and A[i]==A[j])
      duplicate=true
      break;
 if(duplicate)
   break;

我正在确定 if 语句中的操作数如下：

Accessing array element 2 Times
comparing i and J
Comparing A[i] and A[j] 
Comparing AND Operator

这一切都在做N次。我猜测 if 语句中原始操作的数量是否正确？如果不是，请帮我纠正这个问题。谢谢

Answer 1

从技术上讲，我们无法确定这将发生多少次，因为它取决于数组的内容。一旦找到重复项，整个事情就终止了。我们必须查看从 A[0] 到 A[n-1] 的所有元素的完整内容才能提供准确的数字。

你可以说的是，最多（A[]中没有重复），整个代码段将运行 n² 次。因此，其余部分假定没有重复：

比较 i 和 j

此比较将发生 n² 次（再次假设 break 循环没有重复项）。

访问数组元素2次
比较AND运算符
比较 A[i] 和 A[j]

这些其他操作只有在 i != j 为真时才会发生，因为 大多数 现代语言 "short circuit"。当第一个条件失败时（换句话说，当 i 和 j 相同时）其余的 if 条件将被忽略。 AND 从不处理，不访问数组元素，不比较数组元素。

因此，这些将运行n²-n次。 -n 是因为每个 j 循环总是匹配 i 迭代器恰好一个值，短路 if 条件的其余部分。

我将假设使用 C-like 语言并正确格式化代码，就好像这是 C# 代码片段一样：

// n and A[] initialized elsewhere
bool duplicate = false;
for(int i = 0; i < n; i++)
{
    for(int j = 0; j < n; j++)
    {
        if(i != j && A[i] == A[j])
        {
            duplicate = true;
            break;
        }    
    }
    if(duplicate)
    {
        break;
    }
}

IF 语句中的原始操作数

Number of Primitive operations in IF Statement

algorithm

array-algorithms