1.1.2算法时间复杂度分析

1.1.2.1大O记法

定义：

​ 在进行算法分析时，语句总的执行次数T(n)是关于问题规模n的函数，记作:T(n)=O(f(n)) O（f（n））越低这个算法就越优秀。它表示随着问题规模n的增大，算法执行时间 的增长率和f(n)的增长率相同，称作算法的渐近时间复杂度，简称时间复杂度，其中f(n)是问题规模n的某个函数。

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

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

​ 下面我们使用大O表示法来表示一些求和算法的时间复杂度：

算法一：

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

如果忽略判断条件的执行次数和输出语句的执行次数，那么当输入规模为n时，以上算法执行的次数分别为：

算法一：3次

算法二：n+3次

算法三：n^2+2次

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

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

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

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

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

算法一：O(1)

算法二：O(n)

算法三：O(n^2)

1.1.2.2常见的大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(n^2).

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次，那总共程序想要从这三个循环中出来，就需要执行100100100次，也就是n的立方，所 以这段代码的时间复杂度是O(n^3).

4.对数阶

对数，属于高中数学的内容，我们分析程序以程序为主，数学为辅，所以不用过分担心。

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.常数阶

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

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

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

下面是对常见时间复杂度的一个总结：

1.1.2.3 函数调用的时间复杂度分析

之前，我们分析的都是单个函数内，算法代码的时间复杂度，接下来我们分析函数调用过程中时间复杂度。

案例一：

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

在main方法中，有一个for循环，循环体调用了show方法，由于show方法内部只执行了一行代码，所以show方法 的时间复杂度为O(1),那main方法的时间复杂度就是O(n)

案例二：

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; i++) {
				System.out.println(i);
			}
}

在main方法中，有一个for循环，循环体调用了show方法，由于show方法内部也有一个for循环，所以show方法 的时间复杂度为O(n),那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);
	}
}

在show方法中，有一个for循环，所以show方法的时间复杂度为O(n),在main方法中，show(n)这行代码内部执行 的次数为n，第一个for循环内调用了show方法，所以其执行次数为n^2,第二个嵌套for循环内只执行了一行代码， 所以其执行次数为n^{2,那么main方法总执行次数为n+n}2+n²⁼²ⁿ2+n。根据大O推导规则，去掉n保留最高阶 项，并去掉最高阶项的常数因子2，所以最终main方法的时间复杂度为O(n^2)

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)

平均情况： 任何数字查找的平均成本是O(n/2) 最坏情况是一种保证，在应用中，这是一种最基本的保障，即使在最坏情况下，也能够正常提供服务，所以，除非 特别指定，我们提到的运行时间都指的是最坏情况下的运行时间。