带模的for循环的运行时复杂度

Question

问题是从一组 M 个无符号整数中找到一对整数 (a,b)，其中 a-b 是 n 的倍数。给定一个正整数 n，它小于集合 M 的长度 (m)。这是我写的片段。

我不太确定这个算法的时间复杂度w.r.tM的长度和n的值。在排除函数中，最坏情况是 O(m)。然后它在 m 上的 for 循环中，然后是 O(m^2)。此外，X 初始化与 n 成比例，因此此处为 O(n)。总计：O(m^2) + O(n)，忽略其他 O(1)。这是正确的吗？

还有，我应该把r = x % n当成O(1)吗？

欢迎对这里的代码提出任何与编码相关的建议！！！非常感谢！

//array X is intialized of size n, all -1. Here the code is omitted.
    for (int i = 0; i < m; i++)
    {
        if (currentLength > 1)
        {
            index = rand() % currentLength;
            x = setM[index];
            exclude(setM, index, &currentLength);
            r = x % n;
            if (X[r] == -1)
            {
                X[r] = x;
            }
            else
            {
                printf("The pair: (%i, %i)\n", X[r], x);
                break;
            }
        }

        else
        {
            break;
        }
        currentLength -= 1;
    }

// to exclude an element based on index, then shift all elements behind by 1 slot

void exclude(int* array, int index, int* length_ptr)
{
    if (index != *length_ptr - 1)
    {
        for (int i = index; i < *length_ptr - 1; i++)
        {
            array[i] = array[i + 1];
        }
    }
}

Answer 1

您需要找到 x%n==y%n 的两个数字 x 和 y。这很容易。使用密钥 x %n 的散列 table。从集合中添加连续的数字，直到找到重复的数字。这将是理想的一对。复杂度为 O(M)。

Answer 2

Also, should I take r = x % n as O(1)?

是的，是 O(1)

I am not too sure about the time complexity of this algorithm ... In total: O(m^2) + O(n)?

嗯，有点 ，但还不止于此 。问题是 m 和 n 是 不独立的 。

考虑案例 n = 2 并让 m 增加。 你的公式会给出 O(m^2)，但这是正确的吗？不。 因为 % n 只有 2 个可能的结果（即 0 和 1），循环 for (int i = 0; i < m; i++) 只能运行 3 次才能匹配。无论你增加多少 m 都不会超过 3 个循环。在这些循环中的每一个中， exclude 函数在最坏的情况下可能会移动到 m 元素附近。通常 for (int i = 0; i < m; i++) 永远不会超过 n+1 循环。

所以对于 m being larger than n 你宁愿有 O(n*m) + O(n)。当保持 n 不变时，这就变成了 O(m)。所以你的算法只是 O(m) 关于 m.

现在考虑常数 m 和大幅增加 n 的情况。在这种情况下，您的公式给出 O(m^2) + O(n)。由于 m 是常数 O(m^2) 也是常数所以你的算法只是 O(n) 关于 n.

现在，如果您同时增加 m 和 n，您的公式将给出 O(m^2) + O(n)。但是由于m和n都增加了，所以O(m^2)最终会支配O(N)，所以我们可以忽略O(N)。换句话说，您的算法对于两者都是 O(M^2)。

回顾一下：

O(m)   for constant n and increasing m
O(n)   for constant m and increasing n
O(m^2) for increasing n and increasing m

Any coding related advices on the codes here are welcome

好吧，这个 index = rand() % currentLength; 只是个坏主意！

您应该始终测试数组中的最后一个元素，即 index = currentLength - 1;

为什么？仅仅是因为这会将 exclude 变成 O(1)。事实上，您甚至不需要它！排除将在执行 currentLength -= 1;

时自动发生

此更改将提高复杂性，如

O(1)      for constant n and increasing m
O(n)      for constant m and increasing n
O(m)+O(n) for increasing n and increasing m

O(m)+O(n)可以说是O(m)(或者O(n))，随便你怎么想。最主要的是它是线性的。

除此之外你不需要currentLength。将主循环更改为

for (int i = m-1; i >= 0; --i)

并将i用作index。这将您的代码简化为：

for (int i = m-1; i >= 0; --i)
{
    r = setM[i] % n;
    if (X[r] == -1)
    {
        X[r] = setM[i];
    }
    else
    {
        printf("The pair: (%i, %i)\n", X[r], setM[i]);
        break;
    }
}

带模的for循环的运行时复杂度

runtime complexity of for loop with modulo

c

algorithm

time-complexity

modulo

number-theory