c -带模的for循环的运行复杂度

Question

问题是在一个由无符号整数组成的集合M中找到一对整数(a,b)，其中a-b是n的倍数。给定一个小于集合M长度(M)的正整数n。下面是我写的代码片段。

我不太确定这个算法的时间复杂度是多少，而不是M的长度和n的值。在排除函数中，最坏情况是O(M)。然后它在m上的for循环中，然后是O(m²)另外，X初始化随n缩放，所以这里是O(n)总共是O(m^2) + O(n)忽略其他O(1)s。这是正确的吗?

同样，我应该取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

另外，我应该把r = x % n作为O(1)吗?

对，是0 (1)

我不太确定这个算法的时间复杂度…总共是O(m²)+ 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)。所以你的算法就是0 (m)关于m。

现在考虑恒定的m和增大的n的情况。在这种情况下，公式是O(m²)+ O(n)因为m是常数O(m^2)也是常数所以你的算法对于n就是O(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

欢迎任何与代码相关的建议

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

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

为什么?简单地说，这将把exclude变成0(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;
}
}

Answer 2

您需要找到x%n==y%n的两个数字x和y。它容易。使用一个键为x %n的哈希表。从这一集合中添加其他数字，直到找到重复的数字。这是我们想要的一对。复杂度为0 (M)。