在O(N)时间复杂度内计算N以内每个数的因子数？

Question

在O(N)时间复杂度内计算N以内每个数的因子数？

3

因此，我们可以使用筛法算法在O（NlogN）中计算从1到N的每个数字的约数：

int n;
cin >> n;
for (int i = 1; i <= n; i++) {
    for (int j = i; j <= n; j += i) {
        cnt[j]++; //// here cnt[x] means count of divisors of x
    }
}

有办法将其降至O（N）吗？谢谢！

- Barish Namazov

它们都是O(N)的吗？ - user2736738

@coderredoc 是的。 - Barish Namazov

4个回答

2

这里是对@גלעד ברקן的解决方案的简单优化。不使用集合，而使用数组。这比集合版本快约10倍。

n = 100

answer = [None for i in range(0, n+1)]
answer[1] = 1

small_factors = [1]
p = 1
while (p < n):
    p = p + 1
    if answer[p] is None:
        print("\n\nPrime: " + str(p))
        limit = n / p
        new_small_factors = []
        for i in small_factors:
            j = i
            while j <= limit:
                new_small_factors.append(j)
                answer[j * p] = answer[j] + answer[i]
                j = j * p
        small_factors = new_small_factors

print("\n\nAnswer: " + str([(k,d) for k,d in enumerate(answer)]))

值得注意的是，这也是一个枚举质数的O(n)算法。然而，通过使用从所有小于 log(n)/2 大小的质数生成的轮，它可以在O(n/log(log(n)))的时间内创建一个质数列表。

- btilly

我喜欢代码的简洁性，也喜欢使用加法而不是乘法来计算约数的差异。 - גלעד ברקן

我添加了一项额外的优化，将我的电脑上1000万次操作的时间缩短到了8秒，而你的则是6秒。p = p + 2 :) - גלעד ברקן

顺便说一下，while (p < n) 可以改为 while (p < n / 2)，因为任何大于p的数相乘会超出范围（在你的代码版本中又减少了0.4秒）。 - גלעד ברקן

@גלעדברקן 你可以通过注意到 min(p, n/p) 下面的所有内容都在 small_factors 中，因此可以从该列表中消除并通过加法遍历来找到另一个加速。从我的角度来看，p < n/2 实际上会产生错误的答案，因为它会将 None 放在 2 的位置。虽然这可以被特殊处理。 - btilly

“特殊情况？”是的，那我们称它们为“质数”怎么样？ ;) 我不确定你所说的“通过加法遍历”，能否请你解释一下？ - גלעד ברקן

@גלעדברקן 我的意思是，如果 p 是质数，你可以通过不断添加 p 并保持计数器来遍历 1*p, 2*p, 3*p, ..., (p-1)*p。而你写入的计数始终是加倍的。至于特殊情况，我指的是在输出中将 None 打印为 2。 - btilly

0

考虑这些计数的总和，即对于i = 1到n，sum(phi(i))。该总和为O（N log N），因此任何O（N）的解决方案都必须绕过单个计数。

这表明，任何改进都需要依赖于先前的结果（动态规划）。我们已经知道phi（i）是每个质数度数加一的乘积。例如，12 = 2^2 * 3^1。度数分别为2和1。（2 + 1）*（1 + 1）= 6。 12有6个约数：1,2,3,4,6,12。

这将“简化”问题，即是否可以利用先前的知识直接以O（1）的方式计算约数的数量，而无需逐个计算它们。

考虑给定的情况……到目前为止，约数计数包括：

从这些数字中有没有一种O(1)的方式来获取phi（12）= 6？

- Prune

这个枚举必须在从1到N的一个连续数组上完成，这样说是正确的吗？这正是我所想的，我无法想出任何一种从某个较大数字开始进行O(1)枚举的方法。 - Will Ness

@WillNess 这是我的直觉。我在大学里很擅长数论，但我从这里看不出解决方案。如果您可以确定任何相对质数的分解（例如上面的3*4），那么您只需将它们的“phi”值相乘即可得到新值。然而，我不知道有没有一种**O(1)**的方法来确定两个这样的因子。此外，您需要一个不同的方法（虽然简单）来处理素数的幂。例如，8没有这样的因式分解。 - Prune

0

这里有一个算法，理论上比 O(n log(n)) 更好，但对于合理的 n 可能更差。我相信它的运行时间是 O(n lg*(n))，其中 lg* 是 https://en.wikipedia.org/wiki/Iterated_logarithm。

首先，您可以使用 Atkin 筛选法在时间复杂度为 O(n) 的情况下找到所有小于 n 的质数。有关详细信息，请参见 https://en.wikipedia.org/wiki/Sieve_of_Atkin。

现在的想法是我们将仅插入每个计数一次来构建我们的计数列表。我们将逐个处理质因数，并插入具有该质数作为最大质数的所有值。但是，为了做到这一点，我们需要具有以下属性的数据结构：

我们可以在每个值处存储一个值（特别是计数）。

我们可以在$O(1)$的时间内向前和向后遍历插入值的列表。

我们可以“高效地”找到上一个插入的数字小于$i$。

插入应该是“高效”的。

第一条很简单，我们的数据结构中每个插槽都需要一个值的位置。第二项可以使用双向链表完成。第三项可以使用跳表的巧妙变化完成。第四项来自前三项。

我们可以使用节点数组（未初始化）完成这项工作，其具有以下看起来像双向链表的字段：

1. `value` 我们要查找的答案。 2. `prev` 我们已经得到答案的最后一个先前值。 3. `next` 我们已经得到答案的下一个值。

现在假设i在列表中，j是下一个值，跳表技巧将会是我们也会为第一个能被4整除、8整除等等，直到我们到达j的偶数填充prev。所以如果i = 81，j = 96，我们将为82、84、88和96填充prev。

现在假设我们想要在现有的i和j之间的k处插入一个值v。我们该怎么做？我将提供伪代码，从只知道k开始，然后再为i = 81，j = 96和k = 90填写它。

k.value := v
for temp in searching down from k for increasing factors of 2:
    if temp has a value:
        our_prev := temp
        break
    else if temp has a prev:
        our_prev = temp.prev
        break
our_next := our_prev.next
our_prev.next := k
k.next := our_next
our_next.prev := k
for temp in searching up from k for increasing factors of 2:
    if j <= temp:
        break
    temp.prev = k
k.prev := our_prev

在我们的特定示例中，我们愿意从90向下搜索到90、88、80、64、0。但是当我们到达88时，我们实际上被告知prev是81。我们愿意搜索到90、92、96、128、256、...，但是我们只需要设置92.prev 96.prev，就完成了。

现在这是一段复杂的代码，但它的性能是O(log(k-i) + log(j-k) + 1)。这意味着它起初是O(log(n))，但随着更多的值被填充，它会变得更好。

那么我们如何初始化这个数据结构呢？我们初始化一个未初始化值的数组，然后设置1.value := 0，1.next := n+1，以及2.prev := 4.prev := 8.prev := 16.prev := ... := 1。然后我们开始处理我们的质数。

当我们到达素数 p 时，我们从小于 n/p 的前一个插入值开始搜索。从那里向后遍历，我们保持插入值为 x * p, x * p ^ 2,... 直到达到我们的限制。（向后遍历是因为我们不想尝试为 3 和 9 插入 18。向后遍历可以防止这种情况发生。）

现在我们的运行时间是多少？找到质数是 O(n)。找到初始插入项也很容易，是另一个 O(n) 的时间操作，其时间复杂度为 O(n/log(n))。现在考虑所有值的插入？那显然是 O(n log(n))，但我们能做得更好吗？

首先，所有插入到密度为1/log(n)的操作都可以在O(n/log(n)) * O(log(n)) = O(n)的时间内完成。然后，所有插入到密度为1/log(log(n))的操作同样可以在O(n/log(log(n))) * O(log(log(n))) = O(n)的时间内完成。随着日志数量的增加，这样的操作也会增加。我们得到的这些因素的数量是O(lg*(n))，对于我给出的O(n lg*(n))估计。

我没有证明这个估计是你能做到的最好的，但我认为它是。

所以，不是O(n)，但非常接近。

- btilly

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- גלעד ברקן · Accepted Answer

这样怎么样？从2开始，创建一个元组列表(k, d_k)，其中d_k是k的因数个数，从(1,1)开始：

for each prime, p (ascending and lower than or equal to n / 2):
  for each tuple (k, d_k) in the list:
    if k * p > n:
      remove the tuple from the list
      continue
    power = 1
    while p * k <= n:
      add the tuple to the list if k * p^power <= n / p
      k = k * p
      output (k, (power + 1) * d_k)
      power = power + 1
  the next number the output has skipped is the next prime
  (since clearly all numbers up to the next prime are
   either smaller primes or composites of smaller primes)

上述方法还可以生成质数，依靠 O(n) 的内存来找到下一个质数。拥有更高效、独立的质数流可能使我们避免将任何元组 (k, d_k) 添加到列表中，其中 k * next_prime > n ，同时释放所有保存输出大于 n / next_prime 的内存。

Python 代码。