老师，关于求质数复杂度以及逻辑的问题
来源：2-3 简单的复杂度分析
张婧仪
2019-11-17
老师，您在2-3节的最后分析了判断质数的复杂度，于是我写了一个求n以内质数的算法（LeetCode204号问题）。我想问的是第二重for循环的时间复杂度怎么求？代码如下：
public int countPrimes2(int n) {
if(n==0||n==1||n==2)
return 0;
boolean[] primes=new boolean[n];
Arrays.fill(primes,true);
int size= (int) Math.sqrt(n);
for(int i=2;i<=size;i++){
if(primes[i]) {
//这重for循环的时间复杂度怎么求？
for (int j = i * i; j < n; j += i) {
primes[j] = false;
}
}
}
int count=0;
for(int i=2;i<n;i++){
if(primes[i])
count++;
}
return count;
}
写回答
1回答
-
筛素数法的时间复杂度分析理论性太强了，原因就在于你说的这重循环，是一个不定循环（循环次数不固定）
这类时间复杂度分析，严谨的要列出数学表达式，求出其上界。有点儿类似 heapify 的过程为什么是 O(n) 的而非 O(nlogn) 的。
严谨的这个时间复杂度分析已经远远超过这个课程的范畴了，并且，我向你保证，任何面试或者笔试都不会考察这个内容。整体，是在求如下 T(n) 在 n 趋近于无穷时候的积分。
求解这个积分需要 Mertens 定理。最终结果是 nlog(logn)。
如果感兴趣可以参考这篇论文：https://research.cs.wisc.edu/techreports/1990/TR909.pdf
关于 Mertens 定理，可以参考这里：https://arxiv.org/pdf/math/0504289.pdf
不过，对于这个代码，粗糙的分析，说外层循环 sqrt(n) 次，内层循环最多 是 O(n)的，所以整体是 O(nsqrt(n)) 的，但肯定比这个低（因为内层循环次数越来越少）。
同时，因为内层循环最少是 n/sqrt(n)，所以整体肯定比 O(n) 高。介于 O(n) ~ O(nsqrt(n)) 之间。
这个分析结果，对于工程师来说，已经足够了。
加油。
112019-11-18
相似问题