这个 C++ 函数的时间复杂度是多少? [英] What is the time complexity of this C++ function?

问题描述

我编写了一个函数来显示特定数字 n 的质数和因数.

I have written a function to show both number who is prime and factor of a specific number n.

bool PrimeFactor(int n){
    int count = 0;// count divisors

    for (int i = 2 ; i < n; i++){
        if ( n % i == 0 ){
            if ( PrimeFactor(i)){              
                cout << i << endl;
            }
            count ++;
        }
    }

    if (count > 0)//not prime
        return false;
    return true;
}

结果可能会在某些地方重复，但这不是大问题.我不知道如何计算这个递归函数的时间复杂度.

The result may be duplicated in some place, but that's not the big matter. I don't know how to calculate the time complexity of this recursive func .

推荐答案

这基本上是 Ben Voigt 答案的扩展版本.

This is basically a more extended version of Ben Voigt answer.

正如 Ben Voigt 所说，没有条件的版本是 O(n)，这应该很简单.

As Ben Voigt said, the version without the conditional is O(n), this should be straightforward.

现在，带有条件的版本将在 if 语句中执行递归，次数等于 n 的除数 (= n 的除数函数值 = d(n)).

Now, the version with the conditional will execute the recursion inside the if statement a number of times equal to the number of divisors of n (= value of the divisor function for n = d(n)).

下限inf d(n) = 2，因为对于每个素数，这将是真的，并且有无限多个素数，所以不管你做多大n，你总能找到一个d(n) = 2.这意味着对于素数，您的函数将递归 0 次，并且具有复杂度 O(n).

The lower limit inf d(n) = 2, since for every prime, this will be true and there are infinitely many primes, so no matter how big you make n, you can always find one for which d(n) = 2. This means that for primes, your function will recurse 0 times and it has complexity O(n).

上限更复杂(我需要咖啡)，所以让我们暂时跳过它并计算平均复杂度.d(n) = O(log n) 的平均复杂度，因此，如 Ben Voigt 所述，原始函数的平均复杂度为 O(n log n loglog n ...).更详细:您有 for 循环，它是 O(n)，在这个 for 循环中，您将递归 d(n) = O(log n) 次.现在您再次进入该函数并递归O(log (log n))次，依此类推

The upper limit is more complicated (and I need coffee), so lets skip that for a moment and calculate the average complexity. The average complexity of d(n) = O(log n), so, as stated by Ben Voigt, the original function will have an average complexity of O(n log n loglog n ...). More in detail: you have the for loop, which is O(n), in this for loop you will recurse an average of d(n) = O(log n) times. Now you enter the function again and recurse O(log (log n)) times, etc, etc.

另请注意 DarkDust & 对您的问题的评论杰夫福斯特.它也不会按照您想要的方式运行.此外，检查偶数是否除以 n 是没有用的，因为偶数永远不会是素数(当然 2 除外).由于递归，您将在递归调用期间输入内部 if(带有 cout 的那个)，因此您得到的输出将不是您想要的(我'我假设是 n 的不同质数因数).

Also note the comments to your question by DarkDust & Jeff Forster. It will not function the way you want it too. Furthermore, checking if even numbers divide n is useless, since even numbers will never be primes (except for 2 of course). Due to the recursion, you will enter the inner if (the one with cout) during recursive calls, so the output you get, will not be what you want (which I'm assuming is the distinct prime divisors of n).

另一种节省时间的方法是只测试floor(sqrt(n)).如果一个数 i 能整除 n，检查商 j = n/i 是否也是素数.例如.对于 n = 6，您最多可以测试 floor(sqrt(6)) = 2.然后你发现 i = 2 是一个除数，你检查 j = 6/2 = 3.您发现在这种情况下 i 和 j 都是素数.

Another way to save time is by only testing up to floor(sqrt(n)). If a number i divides n exactly, check if the quotient j = n / i is also a prime number. E.g. for n = 6, you'd test up to floor(sqrt(6)) = 2. Then you find that i = 2 is a divisor and you check j = 6 / 2 = 3. You find that both i and j are prime divisors in this case.

这篇关于这个 C++ 函数的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！