为什么朴素质数测试算法不是多项式时间的

Question

我想了解为什么下面这个朴素的素性测试算法不是多项式级别。

IsPrime (n: an integer)
Begin
   For i=2 to n-1 do
     If (n % i == 0) then
        return (no)
     EndIf
   EndFor

   return (yes)
End

这个算法据说是与输入规模n成指数关系的。为什么会这样？而下面的排序测试算法为何被称为多项式而非指数级算法？

IsSorted (T[n]: an array of n integer)
Begin
  For i = 1 to n-1 do
     If (T[i] > T[i+1]) then
        return (no)
     EndIf
  EndFor

  return (yes)
End

- M . Franklin

Answer 1

输入大小通常以比特为单位进行测量。表示数字n的输入大小将是log2（n）。原始素性测试在n方面是线性的，但在log2（n）方面是指数级的。

- Henry

---

是的，稍微写得不同 O(2^k)，其中 k 是输入大小（以位为单位）。 - Henry

谢谢，我现在更好地理解了。 - M . Franklin

我需要多少位来编码一个包含n个整数的数组？ - M . Franklin

一个整数的n倍（=32），因此为32n。 - Henry

据我理解，上述陈述是正确的。 - venkysmarty

Answer 2

作为Henry给出的答案的补充，实际上原始问题中的算法在使用一元编码时具有多项式有界的运行时间！

更确切地说，运行时间的限制不仅取决于算法本身，还取决于所使用的编码方案。考虑以下类似C语言的算法。

INPUT: integer n
for (int i = 0; i < n; i++)
{
    wait one second
}

显然，该算法需要 n 秒才能终止；时间与 n 成线性关系。如果使用 一元编码 对输入进行编码，则所需时间与 n 的编码长度成线性关系。但是，如果使用 二进制编码 对 n 进行编码，则所需时间与 n 的编码长度呈指数关系（因为 n 的编码长度随着 n 的值的对数增长而增长）。

简而言之，没有任何额外信息的情况下，该问题中的算法不是多项式的说法是不正确的。然而，显然使用二进制编码（或任何其他位值记数法）是一种惯例，除非另有说明。

话虽如此，我承认运行时间上限取决于编码方案的依赖性往往会被教授得有点不太准确。术语 伪多项式 也在流传。

- Codor

Answer 3

朴素的主要测试在输入的值（即函数接收到的实际数字）的多项式时间内完成，但在输入的大小（位、字节等）的指数时间内完成。

如果您有一个由b位组成的数字n，我们有b = O(log n)并且n = O(2b)。

因此，运行时间是O(n)或O(2b)。

- Bernhard Barker