代码之家 › 专栏 › 技术社区 › Lamaman

素数算法的复杂度是多少?

complexity-theory conditional algorithm

-4

Lamaman · 技术社区 · 6 年前

我想知道这个算法的复杂度是多少。N>=3作为输入的整数。非常感谢。

initialisation : i=2
LOOP:
if N%i==0
     return 1; 
if i == [sqrt(N)]
     return 0; 
i= i + 1;

1 回复 | 直到 6 年前

Max von Hippel MD. Sahib Bin Mahboob 6 年前

initialisation : i=2
LOOP:
if N%i==0
     return 1;       # 1 <-----
if i == [sqrt(N)]
     return 0;       # 2 <-----
i= i + 1;

情况1:N为偶数。那我们就完了 O(1) -请参见线条( # 1 ).或N是奇数且非素数。然后,当我们达到N的某个除数时,我们就完成了(这将发生在平方根之前,或者同时发生)。

情形2:N是素数。然后我们会击中 [ n^0.5 ] 编号(参见第行 # 2 )完成之前。

runtime of the division involved .这有点不适定,因为我们不知道使用了什么乘除算法。但总运行时间是 O(max{a * sqrt(N), sqrt(N)}) 哪里 O(a) 是的运行时 N % i == 0 检查这里我假设实际的平方根计算实际上是常数时间,并且只进行一次,所以 O(n^0.5) 因为这是在算法结束前,对于一个基本输入,你得到的迭代次数。