该算法的O复杂度很高
该算法的O复杂度很高
提问于 2014-04-18 09:01:30
IsNumberPrime(int num):
if num <= 1: return False
i = 0
end = sqrt(num)
while ArrayOfPrimes[i] <= end:
if (num % ArrayOfPrimes[i]) == 0: return False
i = i + 1
return True此算法检查给定的数字是否为质数ArrayOfPrimes是包含前1000个质数的数组，如2，3，5，7，11……根据我的方法，由于这个算法将只检查直到给定数字的平方根，所以它应该不会超过sqrt(n)/2，所以我的理解是它应该是sqrt(n)。例如，如果数字是19，那么它将只检查直到Ai <=4.8，即只检查2次。
回答 2
Stack Overflow用户
发布于 2014-04-18 22:31:14
该算法的精确复杂度为O(⌊sqrt(num)⌋-1)
这是检查数((num % ArrayOfPrimesi) == 0)条件。
Stack Overflow用户
发布于 2014-07-10 12:33:47
为了得到确切的复杂度，你必须知道ArrayOfPrimes中比sqrt(num)小的条目的数量。最糟糕的情况是，您必须检查所有这些内容。
因此，如果pi(sqrt(num))是比sqrt(num)更低的number of primes，那么复杂度是
O(pi(sqrt(num))) = O(sqrt(num) / log(num))页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/23145847
复制相关文章
相似问题
腾讯云开发者
