数据结构和算法(二)--算法分析

目录

一、算法分析

1、算法的时间复杂度分析

事后分析估算方法：

事前分析估算方法：

1.1、函数渐近增长

1.2、大O记法

1.3、常见的大O阶

1.4、函数调用的时间复杂度

1.5、最坏情况

2、算法的空间复杂度分析

2.1、Java中常见内存占用

2.2、算法的空间复杂度

一、算法分析

        研究算法的最终目的就是如何花更少的时间，如何占用更少的内存去完成相同的需求。

        有关算法时间耗费分析，我们称之为算法的时间复杂度分析，有关算法的空间耗费分析，我们称之为算法的空间复杂度分析。

1、算法的时间复杂度分析

事后分析估算方法：

	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、机器执行指令的速度；

        由此可见，抛开这些与计算机硬件、软件有关的因素，一个程序的运行时间依赖于算法的好坏和问题的输入规模。如果算法固定，那么该算法的执行时间就只和问题的输入规模有关系了。

需求：计算1到100的和。

第一种解法：

//如果输入量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);
	}

因此，当输入规模为n时，第一种算法执行了1+1+(n+1)+n=2n+3次；第二种算法执行1+1+1=3次。如果我们把第一种算法的循环体看做是一个整体，忽略结束条件的判断，那么其实这两个算法运行时间的差距就是n和1的差距。

需求：计算100个1+100个2+100个3+....100个100的结果

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

最重要的就是把核心操作的次数和输入规模关联起来。

1.1、函数渐近增长

概念：给定两个函数f(n)和g(n)，如果存在一个整数N，使得对于所有的n>N，f(n)总是比g(n)大，那么我们说f(n)的增长渐近快于g(n)。

测试一：

结论：

当输入规模n>2时，算法A1的渐近增长小于算法B1的渐近增长。

随着输入规模的增大，算法的常数操作可以忽略不计。

测试二：

结论：

随着输入规模的增大，与最高次项相乘的常数可以忽略。

测试三：

结论：

最高次项指数大的，随着n的增长，结果也会变得增长特别快。

测试四：

结论：

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

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

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

3、算法函数中最高次幂越小，算法效率越高；

1.2、大O记法

定义：在进行算法分析时，语句总的执行次数T(n)是关于问题规律n的函数，进而分析T(n)随着n的变化情况并确定T(n)的量级。算法的时间复杂度，就是算法的时间量度，记作：T(n)=O(f(n))。它表示随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度，其中f(n)是问题规模n的某个函数。

在这里，我们需要明确一个事情：执行次数=执行时间

用大写O()来体现算法时间复杂度的记法，我们称之为大O记法。一般情况下，随着输入规模n的增大，T(n)增长最慢的算法为最优算法。

算法一：

	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++) {
			sum += i;//执行n次
		}
		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);
	}

以上算法执行次数：

算法一：3次

算法二：n+2次

算法三：n^2+2次

如果用大O记法表示上述每个算法的时间复杂度，应该如何使用呢？基于我们对函数渐近增长分析，推导大O阶的表示法有以下几个规则可以使用：

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

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

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

所以上述算法的大O记法分别为：

算法一：O(1)--常数阶

算法二：O(n)----线性阶

算法三：O(n^2)----平方阶

1.3、常见的大O阶

1、线性阶--O(n)

2、平方阶--O(n^2)2次for循环

3、立方阶--O(n^3)--3次for循环

4、对数阶--O(logn)

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

由于每次i*2之后，就距离n更近一步，假设有x个2相乘后大于n,则会退出循环。由于是2^x=n,得到x=log(2)n，所以这个循环的时间复杂度为O(logn);

对于对数阶，由于随着输入规模n的增大，不管底数为多少，它们的增长趋势是一样的，所以我们会忽略底数。

5、常数阶--O(1)

它们的时间复杂度从低到高依次为：O(1)

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

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

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

//有一个存储n个随机数字的数组，请从中查找出指定的数字的索引下标
	public int search(int num) {
		int[] arr = { 11, 10, 8, 9, 7, 22, 33, 23, 0 };
		for (int i = 0; i < arr.length; i++) {
			if (num == arr[i]) {
				return i;
			}
		}
		return -1;
	}

public class A {
    public int a=1;
}
 
通过new A();创建一个对象的内存占用如下：
1、整型成员变量a占用4个字节
2、对象本身占用16个字节
那么创建该对象总共需要20个字节，但由于不是以8为单位，会自动填充为24个字节。

	public static int[] reverse(int[] arr) {
		int n = arr.length;// 申请4个字节
		int tmp;// 申请4个字节
		for (int start = 0, end = n - 1; start <= end; start++, end--) {
			tmp = arr[start];
			arr[start] = arr[end];
			arr[end] = tmp;
		}
		return arr;
	}

	public static int[] reverse(int[] arr) {
		int n = arr.length;// 申请4个字节
		int[] tmp = new int[n];// 申请n*4个字节+数组自身开销24字节
		for (int i = n - 1; i >= 0; i--) {
			tmp[n - 1 - i] = arr[i];
		}
		return tmp;
	}