素数分解算法的运行时

Question

考虑一个采用整数N并将所有整数相除的算法因子2，然后3，然后4，直到大约sqrt(N)。如果要花费单位时间来对整数进行加，减，乘和除，这个算法有多快？如果要花Theta(n)时间怎么办加，减，乘和除两个n位二进制数？

---

我的想法：

为了更好地理解问题，我首先编写了一些伪代码来概述算法。我认为它看起来像这样。

factorize(N) {
   for (i = 2; i <= sqrt(N); i++) {
        let r be the remainder obtained by dividing N by i.
        while (r == 0) {
          N = N / i;
          print i       # Print the prime factors of N.
        }
    }
 }

我很确定算法只是通过反复试验（插入值）而得到的O(sqrt(N))。我认为当N为质数时会出现这种最坏的情况。但是，我对此不太确定。

现在，如果要花费Theta(n)的时间对两个二进制数字进行加，减，乘和除运算，那么运行时将如何更改，我也感到困惑。由于某些原因，这似乎很难分析，因为我们在每次迭代中都执行除法。如果我不得不猜测，我会说O(N^(3/2))，这只是我以前的答案乘以N，但我对这个答案甚至不太确定。

有人可以帮我吗？

Answer 1

您在第一种算法上是非常正确的：最坏的情况是N为质数，并且没有任何因素。您的循环运行sqrt(N)-1次迭代，O（sqrt（N））

对于第二种算法，缺少的见解是N中的位数是ceil(log(N, base=2))。对于计算复杂性，只需使用n = log(N)。

根据您已经介绍的内容，我希望您可以从这里完成：您的除法运算现在是O（log N）而不是O（1）。