什么构成指数时间复杂度？

Question

我在比较两种决定一个数是否是素数的算法，我在看时间复杂度的上界，但我无法理解两者之间的时间复杂度差异，尽管在实践中一种算法比另一种快。

该伪代码以指数时间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

Answer 1

我希望这能解释为什么它们实际上是线性的。

假设您调用函数并查看它们执行了多少次

Prime(n): # 1 time 
    for i in range(2, n-1) #n-1-1 times
        if n % i == 0  # 1 time 
            return False # 1 time

    return True # 1 time


# overall -> n

Prime(n): # Time
    for i in range(2, (n/2+1)) # n//(2+1) -1-1 time
        if n % i == 0 # 1 time
            return False # 1 time
    return True # 1 time

# overall -> n/2 times -> n times

这说明素数是线性函数

O（n^2）可能是因为调用此函数的代码块。

Answer 2

指数与线性是一个如何表示输入和机器模型的问题。如果输入以一元表示（例如，7作为1111111发送）并且机器可以对数字进行恒定的时间划分，那么是的，该算法是线性时间的。然而，n的二进制表示使用大约lg n位，并且数量n与lg n具有指数关系（n=2^（lg n））。

假设两个解的循环迭代次数都在一个常数因子内，则它们在同一个大O类中，即θ（n）。如果输入有lg n位，则为指数，如果有n位，则为线性。

Answer 3

作为对big-O（big-O）和big-θ（big-Theta）的简单直觉，它们是关于当你显著增加问题的大小（例如2倍）时，如何改变你需要做的操作数量。

线性时间复杂度意味着您将大小增加了2倍，您需要执行的步骤数也增加了约2倍。这就是所谓的O（n），通常是可互换的，但不精确的O和之间的区别是O只提供了上界，但保证了上界和下界。

对数时间复杂度（Θ（log（N）））意味着当大小增加2倍时，需要执行的步骤数会增加一些固定数量的操作。例如，使用二进制搜索，只需一次ore循环迭代，就可以在两倍长的列表中找到给定元素。

类似地，对于某些常数，指数时间复杂度（

请注意，这些定义在很大程度上取决于您如何定义“任务的大小”

正如@DavidEisenstat正确指出的，可以在两种可能的上下文中看到您的算法：

>

实际上，在许多情况下，素测试算法应该适用于非常大的数字。例如，今天使用的许多加密算法（如Diffie-Hellman密钥交换或RSA）依赖于非常大的素数，如512位、1024位等等。此外，在这些上下文中，安全性是以这些位的数量而不是特定的素数来衡量的。因此，在这种情况下，衡量任务大小的自然方法是比特数。现在问题来了：我们需要执行多少操作才能使用您的算法检查以位为单位的已知大小的值？显然，如果值N具有m位，则约为N≈ 2米。因此，您的算法从线性Θ（N）转换为指数2Θ（m）。换言之，要解决一个只长一点的值的问题，您需要多做大约2倍的工作。