```java
package net.zhaoxuyang.common.algorithm.other;
/**
* 暴力遞歸,記憶搜索,矩陣求法,流處理求斐波那契數列
* 結論:
* (1)流處理并沒有想象中的快
* (2)暴力遞歸效率及其低下,N稍微大點(40左右)就已經算不出結果
* (3)矩陣求法并沒有記憶搜索快,但是在計算量較大的【別的程序】中卻是最快的
*/
import java.util.stream.Stream;
/**
*
* @author zhaoxuyang
*/
public class Fibonacci {
public static void main(String[] args) throws InterruptedException {
int n = 50;
int res;
long start;
// start = System.nanoTime();
// res = f1(n);
// System.out.println(res);
// System.out.println(System.nanoTime() - start);
start = System.nanoTime();
res = f2(n);
System.out.println(res);
System.out.println(System.nanoTime() - start);
start = System.nanoTime();
res = f3(n);
System.out.println(res);
System.out.println(System.nanoTime() - start);
start = System.nanoTime();
res = Stream.iterate(new int[]{0, 1}, t -> new int[]{t[1], t[0] + t[1]})
.skip(n)
.map(t -> t[0])
.findFirst()
.get();
System.out.println(res);
System.out.println(System.nanoTime() - start);
/*
n=20時,輸出
6765
705588
6765
21391
6765
38888
6765
72026229
n=100時,注釋掉O(2^N)的第一段因為要很久時間,所以后三個的輸出
-980107325
166519
-980107325
43165
-980107325
72650035
*/
}
/**
* O(2^N)
*
* @param n
* @return
*/
public static int f1(int n) {
if (n < 1) {
return 0;
} else if (n == 1 || n == 2) {
return 1;
} else {
return f1(n - 1) + f1(n - 2);
}
}
/**
* 記憶搜索 O(N)
*
* @param n
* @return
*/
public static int f2(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
int res = 1;
int pre = 1;
for (int i = 3; i <= n; i++) {
int tmp = res;
res = res + pre;
pre = tmp;
}
return res;
}
/**
* 矩陣求法 O(logN)
* <pre>
* 如果遞歸式嚴格遵循F(N)=F(N-1)+F(N-2),
* 對于求第N項值,有矩陣乘法的方式可以將時間復雜度降至O(ogN)
* 二階遞推數列,狀態矩陣為2*2的矩陣:
*
* (F(n),F(n-1)) = (F(n-1),F(n-2)) * | a b |
* | c d |
* 斐波那契數列的前4項代入求出狀態矩陣:
* | a b | | 1 1 |
* | c d | = | 1 0 |
*
* (F(n),F(n-1)) = (F(n-1), F(n-2)) * | 1 1 | = (1,1) * | 1 1 |^(n-2)
* | 1 0 | | 1 0 |
* 問題變成求矩陣N次方
* 以整數10的75次方為例:
* 75的二進制為1001011,則10的75次方=10^64 * 10^8 * 10^2 * 10^1
* 把累乘的值相乘即可
*
* 對于矩陣,求矩陣m的p次方請參看matrixPower方法,其中muliMatrix是兩個矩陣相乘的具體實現
* </pre>
*
* @param n
* @return
*/
public static int f3(int n) {
if (n < 1) {
return 0;
}
if (n == 1 || n == 2) {
return 1;
}
int[][] base = {{1, 1}, {1, 0}};
int[][] res = matrixPower(base, n - 2);
return res[0][0] + res[1][0];
}
/**
* @param m
* @param p
* @return
*/
private static int[][] matrixPower(int[][] m, int p) {
int[][] res = new int[m.length][m[0].length];
for (int i = 0; i < res.length; i++) {
res[i][i] = 1;
}
int[][] tmp = m;
for (; p != 0; p >>= 1) {
if ((p & 1) != 0) {
res = muliMatrix(res, tmp);
}
tmp = muliMatrix(tmp, tmp);
}
return res;
}
private static int[][] muliMatrix(int[][] m1, int[][] m2) {
int[][] res = new int[m1.length][m2[0].length];
for (int i = 0; i < m2[0].length; i++) {
for (int j = 0; j < m1.length; j++) {
for (int k = 0; k < m2.length; k++) {
res[i][j] += m1[i][k] * m2[k][j];
}
}
}
return res;
}
}
```
- 1 設計接口
- 1.1 容器接口Container
- 1.2 背包接口Bag
- 1.3 棧接口Stack
- 1.4 隊列接口Queue
- 1.5 Union-Find算法接口UF
- 2 實現接口
- 2.1 結點類Node
- 2.2 數組迭代器ArrayIterator
- 2.3 鏈表迭代器ListIterator
- 2.4 背包(Bag)的實現
- 2.4.1 能動態調整數組大小的Bag
- 2.4.2 鏈式Bag的實現
- 2.5 棧(Stack)的實現
- 2.5.1 能動態調整數組大小的Stack
- 2.5.2 鏈式Stack的實現
- 2.6 隊列(Queue)的實現
- 2.6.1 能動態調整數組大小的Queue
- 2.6.2 鏈式Queue的實現
- 2.7 Union-Find算法的實現
- 2.7.1 DefaultUF
- 2.7.2 QuickFindUF
- 2.7.3 QuickUnionUF
- 2.7.4 WeightedQuickUnionUF
- 2.8 測試
- 2.8.1 測試Stack
- 2.8.2 測試Union-Find
- 3 排序算法
- 3.1 定義排序工具的類結構
- 3.2 選擇排序
- 3.3 插入排序
- 3.4 希爾排序
- 3.5 歸并排序
- 3.5.1 歸并排序的合并方法
- 3.5.2 自頂向下的歸并排序
- 3.5.3 自底向上的歸并排序
- 3.6 快速排序
- 3.6.1 常規快速排序
- 3.6.2 排序前先洗牌
- 3.6.3 快速排序的改進方法-小數據量轉成插入排序
- 3.6.4 快速排序的改進方法-三向切分
- 3.7 堆排序
- 3.8 最終的排序工具
- 4 搜索
- 4.1 二分搜索(binarySearch)
- 4.2 優先隊列(MaxPriorityQueue)
- 4.3 二叉查找樹(BST)
- 4.4 紅黑二叉查找樹(RedBlackBST)
- 4.5 B-樹(BTree)
- 5 圖
- 5.1 無向圖(Graph)
- 5.2 有向圖(Digraph)
- 6 貪心
- Dijkstra算法-單元最短路徑
- 7 動態規劃
- 7.1 最長公共子序列問題
- 7.2 0-1背包問題
- 7.3 加工順序問題
- 8 搜索法
- 8.1 圖的著色問題
- 8.2 深度優先搜索
- 8.3 回溯法
- 8.3.1 回溯法的算法框架
- 8.3.2 子集樹
- 8.3.3 排列樹
- 8.3.4 滿m叉樹(組合樹)
- 8.4 廣度優先搜索
- 8.5 分支限界法
- 9 隨機化算法
- 9.1 數值隨機化算法
- 9.2 蒙特卡羅算法
- 9.3 拉斯維加斯算法
- 9.4 舍伍德算法
- 10 數論算法
- 10.1 Stein求最大公約數
- 10.2 矩陣求斐波那切數列
- LeetCode刷題筆記