这个 C++ 的时间复杂度是多少？功能？
我编写了一个函数来显示谁是质数以及特定数字 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;
}
结果可能在某些地方重复，但这不是什么大问题。我不知道如何计算这个递归 func 的时间复杂度。
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 .
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
这基本上是 Ben Voigt 答案的更扩展版本。
正如 Ben Voigt 所说，没有条件的版本是
O(n)，这应该很简单。现在，带有条件的版本将在
if语句内执行递归，次数等于 n 的除数数 (= n 的除数函数值 =d(n))。下限
inf d(n) = 2，因为对于每个素数，这都是正确的，并且素数有无限多个，所以无论你使n有多大，您总能找到 d(n) = 2 的一个。这意味着对于素数，您的函数将递归 0 次，并且复杂度为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))次，依此类推。另请注意 DarkDust & 对您问题的评论。杰夫·福斯特。它也不会按照您想要的方式运行。此外，检查偶数是否整除
n是没有用的，因为偶数永远不会是素数（当然 2 除外）。由于递归，您将在递归调用期间输入内部if（带有cout的那个），因此您得到的输出不会是您想要的（我是这样的） 'm 假设 是 n) 的不同质因数。另一种节省时间的方法是仅测试
floor(sqrt(n))。如果数字i能整除n，请检查商j = n / i是否也是质数。例如，对于n = 6，您最多可以测试floor(sqrt(6)) = 2。然后您发现i = 2是一个除数，并检查j = 6 / 2 = 3。您会发现在这种情况下，i和j都是素因数。This is basically a more extended version of Ben Voigt answer.
As Ben Voigt said, the version without the conditional is
O(n), this should be straightforward.Now, the version with the conditional will execute the recursion inside the
ifstatement a number of times equal to the number of divisors of n (= value of the divisor function for n =d(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 maken, you can always find one for whichd(n) = 2. This means that for primes, your function will recurse 0 times and it has complexityO(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 ofO(n log n loglog n ...). More in detail: you have the for loop, which isO(n), in this for loop you will recurse an average ofd(n) = O(log n)times. Now you enter the function again and recurseO(log (log n))times, etc, etc.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
nis useless, since even numbers will never be primes (except for 2 of course). Due to the recursion, you will enter the innerif(the one withcout) 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).Another way to save time is by only testing up to
floor(sqrt(n)). If a numberidividesnexactly, check if the quotientj = n / iis also a prime number. E.g. forn = 6, you'd test up tofloor(sqrt(6)) = 2. Then you find thati = 2is a divisor and you checkj = 6 / 2 = 3. You find that bothiandjare prime divisors in this case.这种简化的递归次数不会少于原始的次数，并且其复杂度为
O(n!)。所以这是一个上限。我认为原始的复杂度是
O(n log n loglog n ...)。This simplification will recurse no fewer times than the original, and it has complexity
O(n!). So that's an upper bound.I think the complexity of the original is
O(n log n loglog n ...).我尝试以正式的方式翻译（到递归关系）并解决您的算法，如下所示：
增长的阶数是非多项式，这是一种要避免的算法！
I have attempted to translate (to a recurrence relation) and solve your algorithm in a formal way, like the following:
The order of growth is non polynomial, which is an algorithm to avoid!