开发环境搭建
开发工具
- 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");
}
}