算法基础

算法定义

时间复杂度分析

度量算法执行时间的方式

事后分析估算方法

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. 算法采用的策略和方案；

2. 编译产生的代码质量；

3. 问题的输入规模(所谓的问题输入规模就是输入量的多少)；

4. 机器执行指令的速度；

如果输入量为n为1，则需要计算1次；
如果输入量n为1亿，则需要计算1亿次；
public static void main(String[] args) {
	int sum = 0;//执行1次
	int n=100;//执行1次
	for (int i = 1; i <= n; i++) {//执行了n+1次
		sum += i;//执行了n次
	}
	System.out.println("sum=" + sum);
}

如果输入量为n为1，则需要计算1次；
如果输入量n为1亿，则需要计算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);
}

算法比较的基本规则

1. 算法函数中的常数可以忽略

2. 算法函数中最高次幂的常数因子可以忽略

3. 算法函数中最高次幂越小，算法效率越高。

大O记法

1. 用常数1取代运行时间中的所有加法常数；

2. 在修改后的运行次数中，只保留高阶项；

3. 如果最高阶项存在，且常数因子不为1，则去除与这个项相乘的常数；

如果输入量为n为1，则需要计算1次；
如果输入量n为1亿，则需要计算1亿次；
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);
}

如果输入量为n为1，则需要计算1次；
如果输入量n为1亿，则需要计算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);
}

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. 线性阶
一般含有非嵌套循环涉及线性阶，线性阶就是随着输入规模的扩大，对应计算次数呈直线增长，例如：

public static void main(String[] args) {
	int sum = 0;
	int n=100;
	for (int i = 1; i <= n; i++) {
			sum += i;
	}
	System.out.println("sum=" + sum);
}

它的循环的时间复杂度为O(n),因为循环体中的代码需要执行n次。

2. 平方阶
一般嵌套循环属于这种时间复杂度

public static void main(String[] args) {
	int sum=0,n=100;
	for (int i = 1; i <=n ; i++) {
		for (int j = 1; j <=n ; j++) {
			sum+=i;
		}
	}
	System.out.println(sum);
}

上面这段代码，n=100，也就是说，外层循环每执行一次，内层循环就执行100次，那总共程序想要从这两个循环 中出来，就需要执行100*100次，也就是n的平方次，所以这段代码的时间复杂度是O().

3. 立方阶
一般三层嵌套循环属于这种时间复杂度

public static void main(String[] args) {
	int x=0,n=100;
	for (int i = 1; i <=n ; i++) {
			for (int j = i; j <=n ; j++) {
					for (int j = i; j <=n ; j++) {
								x++;
						}
				}
	}
	System.out.println(x);
}

上面这段代码，n=100，也就是说，外层循环每执行一次，中间循环循环就执行100次，中间循环每执行一次，最 内层循环需要执行100次，那总共程序想要从这三个循环中出来，就需要执行100*100*100次，也就是n的立方，所 以这段代码的时间复杂度是O().

4. 对数阶

int i=1,n=100;
while(i<n){
	i = i*2;
}

由于每次i*2之后，就距离n更近一步，假设有x个2相乘后大于n，则会退出循环。由于是=n,得到,所 以这个循环的时间复杂度为O(logn); 对于对数阶，由于随着输入规模n的增大，不管底数为多少，他们的增长趋势是一样的，所以我们会忽略底数。

5. 常数阶
一般不涉及循环操作的都是常数阶，因为它不会随着n的增长而增加操作次数。例如：

public static void main(String[] args) {
	int n=100;
	int i=n+2;
	System.out.println(i);
}

上述代码，不管输入规模n是多少，都执行2次，根据大O推导法则，常数用1来替换，所以上述代码的时间复杂度为O(1)

最好,最坏,平均时间复杂度

// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
  int i = 0;
  int pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
       pos = i;
       break;
    }
  }
  return pos;
}

最好情况时间复杂度

最坏情况时间复杂度

平均时间复杂度

加权平均值

均摊时间复杂度

// array 表示一个长度为 n 的数组
 // 代码中的 array.length 就等于 n
 int[] array = new int[n];
 int count = 0;
 
 void insert(int val) {
    if (count == array.length) {
       int sum = 0;
       for (int i = 0; i < array.length; ++i) {
          sum = sum + array[i];
       }
       array[0] = sum;
       count = 1;
    }
 
    array[count] = val;
    ++count;
 }

1. insert() 在大部分情况下，时间复杂度都为 O(1)。只有个别情况下，复杂度才比较高，为 O(n)

2. 对于 insert() 函数来说，O(1) 时间复杂度的插入和 O(n) 时间复杂度的插入，出现的频率是非常有规律的，而且有一定的前后时序关系，一般都是一个 O(n) 插入之后，紧跟着 n-1 个 O(1) 的插入操作，循环往复。

空间复杂度分析

java中常见内存占用

1. 基本数据类型内存占用情况：

2. 计算机访问内存的方式都是一次一个字节

3. 一个引用（机器地址）需要8个字节表示：
例如： Date date = new Date(),则date这个变量需要占用8个字节来表示

4. 创建一个对象，比如new Date()，除了Date对象内部存储的数据(例如年月日等信息)占用的内存，该对象本身也有内存开销，每个对象的自身开销是16个字节，用来保存对象的头信息。

5. 一般内存的使用，如果不够8个字节，都会被自动填充为8字节：

6. java中数组被被限定为对象，他们一般都会因为记录长度而需要额外的内存，一个原始数据类型的数组一般需要24字节的头信息(16个自己的对象开销，4字节用于保存长度以及4个填充字节)再加上保存值所需的内存

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;
}

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;
}

算法技巧