ML
算法题
- 用双指针法求解nSum问题
- 线性筛法： 时间为
O(n)。
flags = [True] * (n + 1)
primes = []
pnum = 0
for i in range(2, n):
if flags[i]:
pnum += 1
primes.append(i)
for j in range(pnum):
ind = primes[j] * i
if ind > n:
break
flags[ind] = False
if i % primes[j] == 0:
break
任意一个合数均可以表示为素数的乘积，线性筛法确保一个合数由其最小的因子来消除，这样可以确保其只被标记一遍。上述代码中，一个数
k表示为, 由于
primes数组是有序的，故可以确保k是被其最小因子消除的；当i有一个因子为primes[j]时，就不能继续标记了，因为primes中接下来的质数肯定比i的因子大，就不符合标记准则了。比如k=90, primes[j]=3, i = 2 * 3 * 5 = 30时就不标记,直到在primes[j]=2, i = 3 * 3 * 5 = 45,这样就解决了重复标记的问题；
时间复杂度分析：因为避免了重复标记问题，所以标记操作总共为O(n)，单次循环平均为O(1);外层循环复杂度为O(n)。所以总体复杂度为O(n);
Eratosthenes筛法(埃式筛法)时间复杂度分析
调和级数
调和级数部分和
