我正在比较两种确定数字是否为质数的算法。我正在查看时间复杂度的上限，但是我无法理解两者之间的时间复杂度差异，即使实际上一种算法比另一种算法更快。
此伪代码以指数时间O（2 ^ n）运行：
Prime(n):
for i in range(2, n-1)
if n % i == 0
return False
return True
该伪代码的运行时间是上一个示例的一半，但是我正在努力了解时间复杂度是否仍为O（2 ^ n）：
Prime(n):
for i in range(2, (n/2+1))
if n % i == 0
return False
return True
作为关于big-O（big-O）和big-θ（big-Theta）的简单直觉，它们是关于如何显着增加问题的大小（例如，例如2倍）。
线性时间复杂度意味着您将大小增加了2倍，所需执行的步骤数也增加了约2倍。这就是所谓的Θ(n)，常常可以互换，但不准确O(n)（的区别O和Θ是O只提供了一个上限值，但Θ保证上限和下限）。
对数时间复杂度（Θ(log(N))）表示，将大小增加2倍时，所需执行的步骤数将增加一定数量的操作。例如，使用二进制搜索，您可以仅使用一次矿石循环迭代就在给定元素的两倍长的列表中找到给定元素。
同样，指数时间复杂度（Θ(a^N)对于某个常数a > 1）意味着如果将问题的大小仅增加1，则需要a更多次的操作。（请注意，和之间有细微的差别Θ(2^N)，2^Θ(N)而实际上第二个更通用，两者都位于指数时间内，但两个都不能涵盖全部，更多详细信息，请参见Wiki。）
请注意，这些定义在很大程度上取决于您如何定义“任务的大小”
正如@DavidEisenstat正确指出的那样，可以在两种可能的上下文中看到您的算法：
一些固定宽度的数字（例如32位数字）。在这种情况下，素数测试算法复杂性的一个明显度量就是被测值本身。在这种情况下，您的算法是线性的。
实际上，在很多情况下，素数测试算法应该适用于很大的数字。例如，当今使用的许多加密算法（例如Diffie-Hellman密钥交换或RSA）都依赖于非常大的质数，例如512位，1024位等等。同样在那些上下文中，安全性是根据那些比特的数量而不是特定的质数来衡量的。因此，在这种情况下，衡量任务大小的自然方法是位数。现在出现了问题：使用您的算法，我们需要执行多少次操作才能检查以位为单位的已知大小的值？显然，如果该值N具有m位，则约为N ≈ 2^m。因此，您的算法从线性Θ(N)转换为指数2^Θ(m)。换句话说，要解决一个仅长1位的值的问题，您需要做大约2倍的工作。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句