isPrime函数时间复杂度是否为O(n^0.5)及sigma求T(n)方法

isPrime(n)
int i = 3; 
if n == 2 
return true
if n % 2 == 0 
return false; 
while i^2 <= n
  if n % i == 0
  return false
  else i+=2
return true

时间复杂度判断正确性 #

你的判断完全正确，该函数的最坏时间复杂度确实是O(√n)。
具体逻辑：

• 前两次判断都是常数时间操作，直接覆盖了n=2和所有偶数的场景
• 剩余需要进入循环判断的都是大于2的奇数，循环从i=3开始，每次步长为2，仅遍历奇数，终止条件为i² > n，也就是i的最大取值不会超过√n
• 最坏情况出现在n本身是奇质数时，循环无法提前终止，需要执行到i超过√n才会返回，最多执行约√n/2次，忽略常数系数后渐近复杂度就是O(√n)

用sigma求和推导T(n)表达式 #

完全可以，我们以最坏情况（n为奇质数，无提前返回）推导如下：

1. 首先定义开销规则：所有单次条件判断、算术运算、返回操作的耗时都是常数，边界判断的总固定开销记为C，单次循环内的所有操作总开销记为c
2. 循环中i的取值序列为3、5、7……k，其中k是满足k² ≤n的最大奇数，可得循环执行次数m满足：2m+1 ≤√n，即m ≤ (√n-1)/2
3. 用sigma求和计算总操作数：
   总操作数 = 固定开销 + 循环内总开销 = $C + \sum_{i=1}^{⌊\frac{\sqrt{n}-1}{2}⌋} c$
   化简后得到：$T(n) = C + c \times ⌊\frac{\sqrt{n}-1}{2}⌋$
   忽略常数项和低阶项后，就能得到渐近上界为O(√n)，和之前的判断完全吻合。

注：如果是平均场景，大部分合数都存在较小的质因子，会提前终止循环，平均耗时会远低于最坏情况的O(√n)。

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