開發環境搭建
開發工具
- eclipse: 使用linux壓縮包版本
- JDK1.8,也是linux壓縮包版本
JDK1.8配置環境變量
ubuntu環境下需要打開~/.bashrc
輸入一下代碼
# set JDK
export JAVA_HOME=/usr/lib/jvm/jdk8
export JRE_HOME=${JAVA_HOME}/jre
export CLASSPATH=.:${JAVA_HOME}/lib:${JRE_HOME}/lib
export PATH=${JAVA_HOME}/bin:${PATH} 最後執行source ~/.bashrc生效
字型設定
linux中在window->preferences(偏好)->General->apperance->Colors And Fonts->Basic->TextFont->Edit->調整到17左右
行号設定
右鍵單機紅色區域，選擇show Line Numbers
常用快捷鍵(Linux)
代碼提示 Alt + /
自動導入所需類 Ctrl + Shift + O
錯誤修複 Ctrl+1
快捷生成代碼 Alt + Shift + S
代碼提示增強
找到Window->Preferences->Java->Editor->Content Assist->Auto Activation -> Auto activation triggers for Java:
将下面需要代碼提示的字元輸入到下面的文本框
比如：.(abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ
即可，附加：Auto-Activation:自動化， Auto Activation Triggers-自動激活觸發器
修改工作空間預設編碼
Window->Preferences->General->Workspace->Text file encoding, 選擇other, 填寫UTF-8
複雜度
什麼是算法
算法是用來解決特定問題的一系列執行步驟
使用不同的算法，解決同一個問題，效率相差可能很大
比如求第n個斐波那契數（fibonacci number）
如何評價一個算法的好壞
單從執行效率
- 比較不同算法對同一組輸入的執行處理時間
- 這種方案叫做事後統計法
事後統計法缺點
- 執行時間嚴重依賴硬體以及運作時的不确定因素
- 必須編寫相應的測算代碼
- 測試資料的選擇比較難以保證公正性
算法優劣評估
- 正确性， 可讀性，健壯性（對不合理輸入的反應和處理能力）
- 時間複雜度（time complexity）:估算程式指令的執行次數（執行時間）
- 空間複雜度（space complexity）:估算所需占用的存儲空間
大O表示法（Big O）
大O表示法描述複雜度，它代表資料規模n對應的複雜度
忽略常數，系數，低階
- 9 >> O(1)
- 2n+3>>O(n)
- n2+2n+6 >> O(n2)
- 4n3+3n2+ 22n+100>>O(n3)
- 寫法上n3= n ^ 3
注意：大O表示法僅僅是一種粗略的分析模型， 是一種估算，能幫助我們短時間内了解一種算法的執行效率
對數階的細節
log2n=log29+log9n
log2n, log9n統稱為logn
常見複雜度
| 執行次數 | 複雜度 | 非正式術語 |
| 12 | O(1) | 常數階 |
| 2n+3 | O(n) | 線性階 |
| 4n2+2n+25 | O(n2) | 平方階 |
| 4log2n | O(logn) | 對數階 |
| 3n+2nlog3n+15 | O(nlogn) | nlogn階 |
| 4n3+3n2+22n+100 | O(n3)c | 立方階 |
| 2n | O(2n) | 指數階 |
| – | – | – |
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)<O(2n)<O(n!)<O(nn)
可以借助函數生成工具比較複雜度的大小
- https://zh.numberempire.com/graphingcalculator.php
- 選擇函數圖像繪制工具即可
fibonacci函數的時間複雜度分析(遞歸)
1+2+4+8= 15 = 24-1 = 25-1=2n-1-1=0.5*2n-1
0.5*2n-1，忽略常數，系數，低階複雜度就是O(2n)
fib函數的時間複雜度分析
O(2n)
public static int fib(int n){
if (n <= 1) return n;
return fib(n-1)+fib(n-2);
} O(n)
public static int fib(int n){
if (n <= 1) return n;
int first = 0;
int second = 1;
while(n-- > 1){
second += first;
first = second-first;
}
return second;
} 差别
- 如果是一台1GHZ的普通計算機，運作速度109次每秒，（n為64）
- O(n)大約耗時6.4*10-8秒
- O(2n)大約耗時584.94年
- 有時候算法之間的差距，往往比硬體方面的差距大
Something interesting
- 我是一個斐波那契程式員
- 因為我們都在改昨天和前天的bug
斐波那契的線性代數解法-特征方程
public static int fib3(int n){
double c = Math.sqrt(5);
return (int)((Math.pow((1+c)/2,n)-Math.pow((1-c)/2,n))/c)
} 算法優化方向
盡量少存儲空間
盡量少執行步驟（執行時間）
根據情況時間換空間或空間換時間
多個資料規模情況-O(n+k)
public static void test(int n, int k){
for(int i = 0; i < n; i ++){
System.out.println("test");
}
for(int i = 0; i < k; i ++){
System.out.println("test");
}
}