algorithm - 为什么寻找一个数字的因子是一种具有指数时间复杂度的算法？

Question

为什么这个算法具有指数时间复杂度？

我知道“模数”是一个按位运算符，对单个位进行运算。因此在最坏的情况下，我们需要执行 sqrt(2^n) 除法。所以这是一个 exp 时间算法。

如果那是真的，所有的算法不都会变成指数时间吗？请解释。

Find-Factor(X)
1: if X is even then
2: return ”2 is a factor”
3: end if
4: for i = 3 to Sqrt(X) by +2 do 
5:    test if X%i = 0, if yes, output ”i is a factor”
6: end for
7: return ”X is a prime.”

Answer 1

指数来自迭代次数。在最坏的情况下(即数字为质数的情况)你必须进行 X/2 次迭代(在这个算法中它不是一个好的算法，例如你可以用 sqrt(X) 而不是 X 来限制循环)。这与输入中的位数 = ln(X) 成指数关系。不是数字 X。

顺便说一句，有概率检查可以非常快速地确定给定数字是否为素数。还有一个相当复杂的算法可以确定性地完成相同的工作。您可以谷歌并找到它们。