Plover Temp
2015年6月4日 星期四
2015年6月3日 星期三
2015年6月2日 星期二
2015年5月25日 星期一
2015年5月14日 星期四
Totient Summatory Function
Reference: http://mathworld.wolfram.com/TotientSummatoryFunction.html
例子:[0, 1] 之間所有最簡分數 p/q 滿足 q <= N 的個數 = Phi[N]
定理:Phi[N] ~ O(N^2)
也就是說,如果要直接計算 Phi[N],
最笨的方法就是 O(N^2) 不能比這個再笨了。
枚舉:枚舉所有最簡分數 p/q 可以利用 Stern-Brocot Tree,時間複雜度依然是 O(N^2)。
舉例來說 ProjectEuler #198,如果只是單純枚舉所有最簡分數 p/q < 1/100,
時間複雜度永遠是 O(N^2),當 N = 10^8 這樣是行不通的。
(但比枚舉所有分數再檢查是否為最簡分數聰明得多)
話說回來,有沒有聰明招式可以計算 Phi[N]?
Phi[N] = 1/2 * \sum_{d = 1 to N} MobiusFunction[d] Floor[N/d] (1 + Floor[N/d])
這樣只要 O(N) 的計算量就可以算完,似乎還可以再改進。
的確,如果利用 Mobius inversion formula,
Phi[N] = N(N+1)/2 - \sum_{k = 2 to N} Phi[Floor[N/k]]
因為 Floor[N/k] 有很好的性質,piecewise constant,
當 k >= Sqrt[N] 我們可以計算一大票 Phi[Floor[N/k]],
例如 k in (N/2, N],所有的 Phi[Floor[N/k]] = Phi[1],
k in (N/3, N/2],所有的 Phi[Floor[N/k]] = Phi[2],
k in (N/4, N/3],所有的 Phi[Floor[N/k]] = Phi[3],以此類推。
這樣的時間複雜度 O(N^{3/4}),比 O(N) 還要再快些。
2015年5月12日 星期二
ProjectEuler #423
以前做法時間複雜度太高,不切實際,
必須思考好的演算法。
Prime counting function: http://en.wikipedia.org/wiki/Prime-counting_function
數論重要定理:pi(n) ~ n/log(n)
如果可以找到 O(n pi(n)) = O(n^2 / log(n)) 的演算法,
接著再來改進演算法就可以了(廢話)。
此外,Sieve of Eratosthenes 的時間複雜度是 O(n log log(n)),
不過 ProjectEuler 許多題目需要質數表,對某些解題者來說時間複雜度是 O(1)。
2015年4月15日 星期三
Create simple mvn project
1. mvn archetype:generate -DgroupId=com.mycompany.app -DartifactId=my-app -DarchetypeArtifactId=maven-archetype-quickstart -DinteractiveMode=false
2. mvn package
3. java -cp target/my-app-1.0-SNAPSHOT.jar com.mycompany.app.App
2. mvn package
3. java -cp target/my-app-1.0-SNAPSHOT.jar com.mycompany.app.App
訂閱:
文章 (Atom)