ML
算法題
- 用雙指針法求解nSum問題
- 線性篩法： 時(shí)間為
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
任意一個(gè)合數(shù)均可以表示為素?cái)?shù)的乘積纸泡，線性篩法確保一個(gè)合數(shù)由其最小的因子來消除绩郎，這樣可以確保其只被標(biāo)記一遍。上述代碼中萍启，一個(gè)數(shù)
k表示為, 由于
primes數(shù)組是有序的总珠，故可以確保k是被其最小因子消除的；當(dāng)i有一個(gè)因子為primes[j]時(shí)勘纯，就不能繼續(xù)標(biāo)記了局服，因?yàn)?code>primes中接下來的質(zhì)數(shù)肯定比i的因子大，就不符合標(biāo)記準(zhǔn)則了屡律。比如k=90, primes[j]=3, i = 2 * 3 * 5 = 30時(shí)就不標(biāo)記,直到在primes[j]=2, i = 3 * 3 * 5 = 45,這樣就解決了重復(fù)標(biāo)記的問題腌逢；
時(shí)間復(fù)雜度分析：因?yàn)楸苊饬酥貜?fù)標(biāo)記問題，所以標(biāo)記操作總共為O(n)超埋，單次循環(huán)平均為O(1);外層循環(huán)復(fù)雜度為O(n)。所以總體復(fù)雜度為O(n);
Eratosthenes篩法(埃式篩法)時(shí)間復(fù)雜度分析
調(diào)和級(jí)數(shù)
調(diào)和級(jí)數(shù)部分和
