时间和空间复杂度
[TOC]
首先要知道为什么要有时间和空间复杂度的概念,要想知道一个程序的执行效率理论上来说就应该直接上机测试，但是由于硬件的差异，我们很难做到统一，所以就产生了时间和空间复杂度，用来估计算法的效率。
时间复杂度
时间复杂度主要衡量的是一个算法的运行速度
时间复杂度的概念
时间复杂度的定义：一个算法所花费的时间与其中语句的执行次数成正比例，==算法中的基本操作的执行次数，为算法的时间复杂度==
时间复杂度有最好情况下，平均情况下和最坏情况下
一般指的时间复杂度是最坏情况下
大O渐进表示法
我们只需要将知道一个大概的执行次数就可以了，所以采用大O渐进表示法
// 请计算一下func1基本操作执行了多少次？
void func1(int N){
int count = 0;
for (int i = 0; i < 2N ; i++) {
for (int j = 0; j < N^2 ; j++) {
count++;
}
}
for (int k = 0; k < 2 * N ; k++) {
count++;
}
int M = 10;
while ((M--) > 0) {
count++;
}精确计算就是2 N^3+2*N+10，但是经过大O渐进表示法，就是时间复杂度就是O(N ^3)
几个例子
void func2(int N) {
int count = 0;
for (int k = 0; k < 2 * N ; k++) {
count++;
}
int M = 10;
while ((M--) > 0) {
count++;
}
System.out.println(count);
}2* N+10，去掉后面的数字，去掉系数，所以时间复杂度就是O（N）
// 计算func3的时间复杂度？
void func3(int N, int M) {
int count = 0;
for (int k = 0; k < M; k++) {
count++;
}
for (int k = 0; k < N ; k++) {
count++;
}
System.out.println(count);
}由于M和N未知，所以就是O（M+N）
void func4(int N) {
int count = 0;
for (int k = 0; k < 100; k++) {
count++;
}
System.out.println(count);
} 循环了100次，是一个确定的常数，所以就是O（1）
最坏情况下就是不优化，N*(N-1)=N^2-N,所以时间复杂度(最坏情况)就是O（N ^2 ）
最好的情况就是数组就是升序的，只走了一遍全部数字，第二个循环就直接跳出去了，没有发生交换，所以此时 最好的情况就是O（N）
冒泡排序完整版（升序）
import java.util.Arrays;
class BubbleSort {
public static void bubblesort(int[] arr) { //记得加上static，确保main里面可以带调用
for (int end =arr.length;end>0;end--) {
boolean flag=true;
for (int i = 1; i <end ; i++) {
if (arr[i - 1] > arr[i]) {
int tmp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = tmp;
}
flag = false;
}
if (flag==true) {
break;
}
}
}
public static void main(String[] args) {
int[] arr = {1, 3, 2, 4, 23, 6};
//BubbleSort bubbleSort = new BubbleSort();
//要是上面的方法没有加上static也可以定义一个对象，new一下直接补全
//但还是在方法前面加上static最省心
bubblesort(arr);
System.out.println(Arrays.toString(arr));
}
}
冒泡排序+二分查找
import java.util.Arrays;
import java.util.Scanner;
//冒泡排序
public class BubbleSort {
static void bubblesort(int[] arr) {
for (int end =arr.length;end>0;end--) {
boolean flag=false;
for (int i = 1; i <end ; i++) {
if (arr[i - 1] > arr[i]) {
int tmp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = tmp;
}
flag = true;
}
if (!flag) {
break;
}
}
}
//二分查找
static int Binarysort(int[] arr, int value) {
int l=0;
int r=arr.length-1;
while (l <= r) {
int mid = l + (r - l) / 2;
if (arr[mid] < value) {
l = mid + 1;
} else if (arr[mid] > value) {
r = mid - 1;
}else{
return mid;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = {1, 3, 2, 4, 23, 6};
bubblesort(arr);//二分查找的前提是有序数组
Scanner scanner = new Scanner(System.in);//创建一个scanner的对象
while (scanner.hasNext()) {
int value = scanner.nextInt();
if (Binarysort(arr, value) == -1) {
System.out.println("找不到这个数字");
}else{
System.out.println("找到了，下标为"+Binarysort(arr, value));
}
}
}二分查找的时间复杂度
最坏的情况就是要找的数字在最右边，此时要查找的次数最多
所以二分查找的时间复杂度是O(log2n)
递归的时间复杂度
递归的时间复杂度=递归的次数*每次递归执行的次数
计算阶乘递归的时间复杂度
public static int factorial(int n) {
return n > 2 ? n : factorial(n - 1) * n;
}一共要递归n-1次，每次递归执行一次三目运算符，所以这个阶乘的时间复杂度是O(n)
计算斐波那契数的时间复杂度
public static int feb(int n) {
return n < 2 ? n : feb(n - 1) + feb(n - 2);
}
假设n=3，要是在最坏情况下，那就是2^ 0+2^ 1+2^ 2
类比开来，就是2^0+2^ 0+2^ 1+2^ 2 +……+2^(n-1) ,也就是一个等比数列求和问题
所以结果为2^n+1,所以时间复杂度为O(2 ^n) ---指数级别增长
空间复杂度
==空间复杂度算的是额外的变量的个数。==空间复杂度也使用大O渐进表示法。
计算冒泡排序的空间复杂度
public class BubbleSort {
static void bubblesort(int[] arr) {
for (int end =arr.length;end>0;end--) {
boolean flag=false;
for (int i = 1; i <end ; i++) {
if (arr[i - 1] > arr[i]) {
int tmp = arr[i - 1];
arr[i - 1] = arr[i];
arr[i] = tmp;
}
flag = true;
}
if (!flag) {
break;
}
}
}在代码运行的时候，有end、flg、i 、tmp 4个额外的变量，所以空间复杂度是O(1)
计算斐波那契数的空间复杂度
int[] fibonacci(int n) {
long[] fibArray = new long[n + 1];
fibArray[0] = 0;
fibArray[1] = 1;
for (int i = 2; i <= n ; i++) {
fibArray[i] = fibArray[i - 1] + fibArray [i - 2];
}
return fibArray;
}会根据数组的大小，开辟不同的变量大小,是n+1,s所以时间复杂度是O（N)
递归的空间复杂度
long factorial(int N) {
return N < 2 ? N : factorial(N-1)*N;
}每递归进去一次，就要开辟一次内存，所以这个阶乘的空间复杂度是O（N）
常见的时间复杂度：O（1）、O(log2n)、O（N）、O(N*log2n>)、O(N^2)、O（2 ^n）
以上的时间复杂度的效率是越来越慢的
总结来说，要想知道时间复杂度不能只看代码，还要关注代码的实现思想。
