如何找到给定算法的比较次数和复杂度

Question

我正在尝试确定比较的总数（不计算循环的停止条件）以及复杂度如何随着 N 的增加而增加。

1. 
for (int ind = 0; ind < N; ind++)
{
    if (arr[ind] < 0)
        arr[ind] = arr[ind] * 2;
}
2. 
bool there_are_duplicates = false;
for (int ind1 = 0; ind1 < N; ind1++)
{
    for (int ind2 = 0; ind2 < N; ind2++)
        if (ind1 != ind2 && arr[ind1] == arr[ind2])
            there_are_duplicates = true;
}
3. 
for (int ind = 0; ind < N; ind++)
{
    int sum = 0;
    int nb = 0;
    for (int n = 0; n < 4; n++)
    {
        if (ind >= n)
        {
            sum = sum + arr[ind - n];
            nb++;
        }
    }
    arr[ind] = sum / nb;
}

第一个，复杂度为N，比较次数也为N或刚好等于1?

第二个，复杂度是N^2，比较次数是2(N^2)还是刚好等于2？

第二个，复杂度为N，比较次数也是4N，还是刚好等于1或4？

Answer 1

让我们数一数：

你比较数组的每个项，所以你有N个比较和O(N)个复杂度
你有嵌套循环，你比较每个项（其中N项）与所有其他人，但他们自己（即 N - 1 项目）。您有 N * (N - 1) 比较和 O(N^2) 复杂度
在这里，您处理每个项 4 次。因此，您有 4 * N 个比较和 O(N) 个复杂性

如何找到给定算法的比较次数和复杂度

How to find number of comparisons and complexity of a given algorithm

c

arrays

algorithm

time-complexity