计算找到第一个'n'素数的时间复杂度

Question

找到第一个'n'素数的算法是:

while (number <= n) {
  boolean isPrime = true; 
  for (int divisor = 2; divisor <= (int)(Math.sqrt(number)); divisor++) {
    if (number % divisor == 0) {
      isPrime = false;      
      break;
    }
  }
  if(isPrime) 
    System.out.print(number + " ");
}

这本书"Java编程简介"计算了这个算法的big-O:

由于在for循环中需要√i步骤来检查数字i是否为素数,因此算法采用√2+√3+√4+ ... +√n步骤来找到小于或等于n的所有素数.

观察,

√2+√3+√4+ ... +√n<=n√n

因此,该算法的时间复杂度为O(n√n).

阙:

1.他说,"它需要√i中的步骤for循环,以检查是否数字我是总理".

你不认为它应该是(√i-1)步骤.

2.请解释

√2+√3+√4+ ... +√n<=n√n

(我知道如果你用随机数替换'n',这种关系就成立了.我需要解释)

Answer 1

1. 复杂性,减去1没有影响(这是一个非正式的介绍).
   (实际上是这样floor(?n) - 1.)

2. 你有n - 1个术语.添加√nn - 1次:

   √n+√n+√n+ ... +√n=(n-1)√n<=n√n

由于√2,√3,√4,......都小于√n,因此

?2 + ?3 + ?4 + ... + ?n <= ?n + ?n + ?n + ... + ?n <= n?n