指数时间复杂度的构成及素数判断算法时间复杂度疑问

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

指数时间复杂度（通常记作O(2^n)、O(k^n)，k为大于1的常数）的核心特征是：输入规模每增加1，算法的运行时间就会乘以一个固定的大于1的系数。

举个直观的例子：如果你要枚举一个包含n个元素的集合的所有子集，每个元素都有“选”或“不选”两种可能，总共有2^n个子集——这时候枚举的时间复杂度就是O(2^n)。随着n从10涨到20，计算量会从1024暴涨到1048576，增长速度极其迅猛，和线性（O(n)）、多项式（O(n²)、O(n^3)）复杂度的平缓增长完全不是一个量级。

简单来说，当算法的运行时间增长速度和输入规模的指数函数成正比时，它就是指数时间复杂度的算法。

2. 素数判断算法的时间复杂度分析 #

首先要纠正一个关键误解：你给出的两个素数判断算法都不是O(2^n)，它们的时间复杂度都是线性级别的，我们来具体拆解：

第一个算法的时间复杂度 #

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

这个算法的循环最多会执行n-3次（从2遍历到n-2）。当n足够大时，常数项可以忽略，所以它的时间复杂度是O(n)——也就是线性时间复杂度。

第二个算法的时间复杂度 #

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

这个算法的循环最多执行(n/2 + 1) - 2 = n/2 - 1次，确实是第一个算法循环次数的大约一半。但大O表示法的核心是描述输入规模增长时的运行时间趋势，常数因子会被直接忽略。所以哪怕它的实际运行时间是前者的一半，时间复杂度仍然是O(n)。

额外补充：更高效的素数判断思路 #

其实你还可以进一步优化这个算法：如果n有一个大于sqrt(n)的因数，那它必然对应一个小于sqrt(n)的因数。所以只需要循环到sqrt(n)就足够了，这样时间复杂度会降到O(sqrt(n))，比你给出的两个算法高效得多。

内容的提问来源于stack exchange，提问作者Justin