素因子算法的复杂性

本文介绍了素因子算法的复杂性的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我刚刚学习了如何用this算法求一个数的素因数，基本上是这样的：

void printPrimeFactors(N) { while N is even print 2 as prime factor N = N/2 // At this point N is odd for all the ODDS i from 3 to sqrt(N) while N is divisible by i print i as prime factor N = N / i if N hasn't been divided by anything (i.e. it's still N) N is prime }

一切都很清楚，但我不确定如何计算上述程序的BIG-O复杂度。

作为最昂贵的运算(我想)，我会说最坏的情况可能是最多有对数(N)个除法，但我不能完全确定这一点。

推荐答案

您可以这样操作。首先，我们只对N非常大时应用程序的行为感兴趣。在这种情况下，我们可以简化很多：如果两个部分具有不同的渐近性能，我们只需要选择表现最差的部分。

第一个while最多可以循环m次，其中m是最小的整数，所以2m>；=N。因此，在最坏的情况下，它将循环LOG2N次--这意味着它的执行方式为O(LOGN)。请注意，当N足够大时，日志类型无关紧要。

for循环运行O(SQRTN)次。在规模上，这比日志N大得多，因此我们可以删除日志。

最后，我们需要计算循环内的while。因为这个While循环只对除数执行，所以它将有一个等于它们的数字的大O。稍微想一想，我们可以看到，在最坏的情况下，while将对数N循环3次，因为3是可能的最小除数。

因此，While循环只执行O(logN)次，但外部for执行O(SQRTN)次(通常情况下，While循环不会运行，因为当前的数字不会相除)。

总而言之，花费时间最长的部分是for循环，这将使算法运行为O(SQRTN)。