開發環境搭建
開發工具
- 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
斐波那契的線性代數解法-特征方程
這個暫時沒看懂========
================這個又看了一下視頻， 基本上就是一個固定的公式，老師說并不是全部的都有這種巧合，因此記住這一個就行，
F(n) = c1x1n+c2x2n.
x1=(1+51/2)/2
x2=(1-51/2)/2
c1=5-1/2
c2=-5-1/2
F(n)=5-1/2 [(1+51/2)/2-(1-51/2)/2]
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(1)!!!
演算法優化方向
盡量少存盤空間
盡量少執行步驟（執行時間）
根據情況時間換空間或空間換時間
多個資料規模情況-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");
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/397529.html
標籤：其他
上一篇：年底了，不要跳槽...