java - 为什么这两种算法的运行时间有所不同？

作为一个较大问题的一部分，我必须找到整数n的素数因子之和。我写了自己的版本，但是我对问题的解决方法超时了。我在网上看了一下，发现了同一方法的另一种版本，将一个整数的素因子相加，当我只改变其中一种方法时，解决方案就足够快了。但是仅基于代码，我发现运行时间没有任何区别。

我的（较慢）版本：

static int factors(int n) {
        int total = 0;
        while (n % 2 == 0) {
            total += 2;
            n /= 2;
        }
        int j = 3;
        while (n > 1) {
            while (n % j == 0) {
                total += j;
                n /= j;
            }
            j += 2;
        }
        return total;
    }

我发现的（更快）版本：

static int factors(int n) {
        int sum = 0;
        int i = 2;
        while (true) {
            if (n % i == 0) {
                n /= i;
                sum += i;
                if (isPrime(n)) {
                    sum += n;
                    break;
                }
                i = 1;
            }
            i++;
        }
        return sum;
    }

为了简洁起见，我没有在底部添加isPrime方法。它只是循环到sqrt(n)的基本暴力手段，甚至不是Eratosthenes的Sieve。

如果有的话，我会以为我的版本会更快，因为它可以消除素数因子的所有重复项，并且不需要重复测试数字是否为素数。

最佳答案

我相信这取决于您的意见。

我认为在纸上，这两种算法的复杂度是相同的：O(n log(n))（假设isPrime(n)的复杂度为O(log(n))-请问在计算Big O方面比我更好的人可以确认还是否认很好），因此它们应该大致相当，但是如您所知，此分析需要假设最坏的情况。

在实践中：

例如。想象您的数字n是3 ^ 1000，您的方法会将其除以3约1000次，第二种方法将其除以3，然后是9，然后是27，依此类推，从而减少了所需的运算次数。

通常，我会假设，如果n中多次存在相同的因子，则您的方法会更慢。

关于java - 为什么这两种算法的运行时间有所不同？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/57206504/