算法分析（时间为尊，空间为王）
在Java中更多考虑的是时间复杂度，由于开发环境的原因，空间复杂度考虑的因素较为宽泛，如果在嵌入式语言中，由于开发内存的大小，需要考虑空间复杂度，降低代码的冗余性。
1.1算法的时间复杂度分析
计算算法时间耗费情况，分为
①事后分析估算方法：使用System.currentTimeMillis()来得到该代码的运行所需时间。
②事前分析估算方法：
运行所消耗的时间取决于下列因素：
1.算法采用的策略和方案；
2.编译产生的代码质量；
3.问题的输入规模(所谓的问题输入规模就是输入量的多少)；
4.机器执行指令的速度；
下面展示一些 事后分析估算方法举例。
public static void main(String[] args) {
long start = System.currentTimeMillis();
int sum = 0;
int n=100;
for (int i = 1; i <= n; i++) {
sum += i;
}
System.out.println("sum=" + sum);
long end = System.currentTimeMillis();
System.out.println(end-start);
}
1.1.1 函数渐近增长
比较算法随着输入规模的增长量时，可以有以下规则：
1.算法函数中的常数可以忽略；
2.算法函数中最高次幂的常数因子可以忽略；
3.算法函数中最高次幂越小，算法效率越高。
1.1.2算法时间复杂度
1.1.2.1 大O记法
**定义：**在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)随着n的变化情况并确定T(n)的量级。算法的时间复杂度，就是算法的时间量度，记作:T(n)=O(f(n))。
**时间复杂度：**它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度。
下面展示一些 算法一：记为O（1）。
public static void main(String[] args) {
int sum = 0;//执行1次
int n=100;//执行1次
sum = (n+1)*n/2;//执行1次
System.out.println("sum="+sum);
}
下面展示一些 算法二：记为O（n）。
public static void main(String[] args) {
int sum = 0;//执行1次
int n=100;//执行1次
for (int i = 1; i <= n; i++) {
sum += i;//执行了n次
}
System.out.println("sum=" + sum);
}
下面展示一些 算法三：记为O（n^2）。
public static void main(String[] args) {
int sum=0;//执行1次
int n=100;//执行1次
for (int i = 1; i <=n ; i++) {
for (int j = 1; j <=n ; j++) {
sum+=i;//执行n^2次
}
}
System.out.println("sum="+sum);
}
基于我们对函数渐近增长的分析，推导大O阶的表示法有以下几个规则可以使用：
1.用常数1取代运行时间中的所有加法常数；
2.在修改后的运行次数中，只保留高阶项；
3.如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数；
1.1.2.2常见的大O阶
1.线性阶
一般含有非嵌套循环涉及线性阶，线性阶就是随着输入规模的扩大，对应计算次数呈直线增长，循环的时间复杂度为O(n),因为循环体中的代码需要执行n次.
2.平方阶
一般嵌套循环属于这种时间复杂度.
3.立方阶
一般三层嵌套循环属于这种时间复杂度.
4.对数阶
下面展示一些 对数阶举例。
int i=1,n=100;
while(i<n){
i = i*2;
}
5.常数阶
一般不涉及循环操作的都是常数阶，因为它不会随着n的增长而增加操作次数。
1.1.2.3 函数调用的时间复杂度分析
下面展示一些 最终main方法的时间复杂度为O(n^2)。
public static void main(String[] args) {
int n=100;
show(n);
for (int i = 0; i < n; i++) {
show(i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println(j);
}
}
}
private static void show(int i) {
for (int j = 0; j < i; i++) {
System.out.println(i);
}
}
1.1.2.4 最坏情况（一般按照最坏结果进行判断）
下面展示一些 有一个存储了n个随机数字的数组，请从中查找出指定的数字。
public int search(int num){
int[] arr={11,10,8,9,7,22,23,0};
for (int i = 0; i < arr.length; i++) {
if (num==arr[i]){
return i;
}
}
return -1;
}
**最好情况：**查找的第一个数字就是期望的数字，那么算法的时间复杂度为O(1)
**最坏情况：**查找的最后一个数字，才是期望的数字，那么算法的时间复杂度为O(n)
1.2 算法的空间复杂度分析
1.2.1java中常见内存占用
1.基本数据类型内存占用情况：
2.计算机访问内存的方式都是一次一个字节
3.一个引用（机器地址）需要8个字节表示：
例如： Date date = new Date(),则date这个变量需要占用8个字节来表示
4.创建一个对象，比如new Date()，除了Date对象内部存储的数据(例如年月日等信息)占用的内存，该对象本身也有内存开销，每个对象的自身开销是16个字节，用来保存对象的头信息。
5.一般内存的使用，如果不够8个字节，都会被自动填充为8字节：
6.java中数组被被限定为对象，他们一般都会因为记录长度而需要额外的内存，一个原始数据类型的数组一般需要24字节的头信息(16个自己的对象开销，4字节用于保存长度以及4个填充字节)再加上保存值所需的内存。
1.2.2 算法的空间复杂度
对指定的数组元素进行反转，并返回反转的内容。
下面展示一些 方式一:对指定的数组元素进行反转，并返回反转的内容，空间复杂度O（1）。
public static int[] reverse1(int[] arr){
int n=arr.length;//申请4个字节
int temp;//申请4个字节
for(int start=0,end=n-1;start<=end;start++,end--){
temp=arr[start];
arr[start]=arr[end];
arr[end]=temp;
}
return arr;
}
下面展示一些 方式二:对指定的数组元素进行反转，并返回反转的内容，空间复杂度O（n）。
public static int[] reverse2(int[] arr){
int n=arr.length;//申请4个字节
int[] temp=new int[n];//申请n*4个字节+数组自身头信息开销24个字节
for (int i = n-1; i >=0; i--) {
temp[n-1-i]=arr[i];
}
return temp;
}